three little problems
Author Message
three little problems

here are three little real-world problems which cropped up
in my work over the last week.  the k solutions are exactly
as they appear in the production code.

1. cross-product combination.

given a list of n lists produce a matrix of the combinations.
e.g. for a list of 3 lists of lengths 3 2 4:

comb:(,/,/:\:)/

comb(1 2 3;4 5;6 7 8 9)
(1 4 6
1 4 7
1 4 8
1 4 9
1 5 6
1 5 7
1 5 8
1 5 9
2 4 6
2 4 7
2 4 8
2 4 9
2 5 6
2 5 7
2 5 8
2 5 9
3 4 6
3 4 7
3 4 8
3 4 9
3 5 6
3 5 7
3 5 8
3 5 9)

2. write a function sort which takes a list k of n lists and a
list d of n directions (0=up, 1=down) and sorts the list according
to the directions (multiway sort).

k:(0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1
2 3 0 0 4 1 4 2 1 2 4 3 2 0 0 3 4 1 1 0 3 0 0 1 3 4 0 2 0 0
0 3 0 2 4 1 0 1 3 2 1 0 3 1 3 1 3 2 0 4 4 0 2 4 2 2 3 4 1 4)

d:0 1 0

index:{x y z x}

sort[k;d]
(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1
4 4 4 4 4 3 3 3 3 3 2 2 2 2 2 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0
0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4)

m:1000000#'k   / let each list be a million long

\t sort[m;d]
906              / less than 1 second, 450 mhz pentium II

the index function x y z x is surprisingly general.  for example,
suppose we want to select rows in k where some set of conditions
holds.  the select function is:

for example, select rows in k where 1> row 0 and 3= row 1:

r:0 1

c:(&1>;&3=)

select[k;c;r]
(0 0 0 0 0
3 3 3 3 3
3 0 1 4 2)

250 ms to select 166666 records from a million row table:

\t select[m;c;r]
250

3. for gui, a data driver for java's gridbaglayout.  suppose m
contains 5 objects, a b c d and e, which tile the window according
to the following picture:

a a a b b
a a a c c
a a a c c
d d d d e
d d d d e

from that matrix, compute the extent (origin row, origin column,
number of rows, number of columns) of each object:

m:(`a `a `a `b `b
`a `a `a `c `c
`a `a `a `c `c
`d `d `d `d `e
`d `d `d `d `e)

extent:{s:(^x)_vs v?/:u:?v:,/x;e:(^x)-(^x)_vs(|v)?/:u;+(u;+s,e-s)}

extent m
((`a
0 0 3 3
)
(`b
0 3 1 2
)
(`c
1 3 2 2
)
(`d
3 0 2 4
)
(`e
3 4 2 1
))

Mon, 02 Sep 2002 03:00:00 GMT
three little problems

Quote:
> here are three little real-world problems which cropped up in my
> work over the last week.

Quote:
> 1. cross-product combination.

> given a list of n lists produce a matrix of the combinations.
> e.g. for a list of 3 lists of lengths 3 2 4:

sequence

:-)

Actually, the type of sequence is more general:
sequence :: Monad m => [m a] -> m [a]

sequence takes a list of "actions" (whatever it means for the given
monad) and gives the action that executes these actions in sequence,
collecting their return values into a list.

The list is an example of a monad. In this context, a list "action"
means to deliver multiple results, and sequencing two "actions"
means to pass each of the result from the first to the second.

Quote:
> 2. write a function sort which takes a list k of n lists and a
> list d of n directions (0=up, 1=down) and sorts the list according
> to the directions (multiway sort).

import List

multiSort :: Ord a => [[a]] -> [Int] -> [[a]]
multiSort k d = transpose \$ sortBy cmp \$ transpose k
where
cmp    a b = uncurry compare \$ unzip \$ zipWith3 swap d a b
swap 0 a b = (a,b)
swap 1 a b = (b,a)

Quote:
> 3. for gui, a data driver for java's gridbaglayout.  suppose m
> contains 5 objects, a b c d and e, which tile the window according
> to the following picture:

>   a a a b b
>   a a a c c
>   a a a c c
>   d d d d e
>   d d d d e

> from that matrix, compute the extent (origin row, origin column,
> number of rows, number of columns) of each object:

import List; import FiniteMap

First version, using FiniteMap
-------------

extent :: Ord a => [[a]] -> [(a,Int,Int,Int,Int)]
extent =
map (\(x,(i,j,k,l)) -> (x,i,j,k-i+1,l-j+1)) .
fmToList .
addListToFM_C (\(i,j,_,l)(_,j',k',l')->(i,min j j',k',max l l')) emptyFM .
concat .
zipWith (\i -> zipWith (\j x -> (x,(i,j,i,j))) [0..]) [0..]

Second version, using sort and assuming that objects are rectangles
--------------

extent :: Ord a => [[a]] -> [(a,Int,Int,Int,Int)]
extent =

groupBy (\(a,_,_) (b,_,_) -> a==b) .
sort .
concat .
zipWith (\i -> zipWith (\j x -> (x,i,j)) [0..]) [0..]

I'm not sure if it's fast enough and how it can be easily made faster.
I don't like these solutions much.

--

\__/              GCS/M d- s+:-- a22 C+++\$ UL++>++++\$ P+++ L++>++++\$ E-
^^                  W++ N+++ o? K? w(---) O? M- V? PS-- PE++ Y? PGP+ t
QRCZAK                  5? X- R tv-- b+>++ DI D- G+ e>++++ h! r--%>++ y-

Mon, 02 Sep 2002 03:00:00 GMT
three little problems

Quote:

>> here are three little real-world problems which cropped up in my
>> work over the last week.

why do i get the impression that you like haskell?

Quote:

>> 1. cross-product combination.

>> given a list of n lists produce a matrix of the combinations.
>> e.g. for a list of 3 lists of lengths 3 2 4:

>sequence

>:-)

>Actually, the type of sequence is more general:
>    sequence :: Monad m => [m a] -> m [a]

>sequence takes a list of "actions" (whatever it means for the given
>monad) and gives the action that executes these actions in sequence,
>collecting their return values into a list.

>The list is an example of a monad. In this context, a list "action"
>means to deliver multiple results, and sequencing two "actions"
>means to pass each of the result from the first to the second.

i think i understand all the words, but i don't see how typing

sequence

the session, wherein you create the list of lists, then 'sequence'
them to produce the matrix.

Quote:

>> 2. write a function sort which takes a list k of n lists and a
>> list d of n directions (0=up, 1=down) and sorts the list according
>> to the directions (multiway sort).

>import List

>multiSort :: Ord a => [[a]] -> [Int] -> [[a]]
>multiSort k d = transpose \$ sortBy cmp \$ transpose k
>    where
>    cmp    a b = uncurry compare \$ unzip \$ zipWith3 swap d a b
>    swap 0 a b = (a,b)
>    swap 1 a b = (b,a)

how does this do on large lists?

- Show quoted text -

Quote:

>> 3. for gui, a data driver for java's gridbaglayout.  suppose m
>> contains 5 objects, a b c d and e, which tile the window according
>> to the following picture:

>>   a a a b b
>>   a a a c c
>>   a a a c c
>>   d d d d e
>>   d d d d e

>> from that matrix, compute the extent (origin row, origin column,
>> number of rows, number of columns) of each object:

>import List; import FiniteMap

>First version, using FiniteMap
>-------------

>extent :: Ord a => [[a]] -> [(a,Int,Int,Int,Int)]
>extent =
>    map (\(x,(i,j,k,l)) -> (x,i,j,k-i+1,l-j+1)) .
>    fmToList .
>    addListToFM_C (\(i,j,_,l)(_,j',k',l')->(i,min j j',k',max l l')) emptyFM .
>    concat .
>    zipWith (\i -> zipWith (\j x -> (x,(i,j,i,j))) [0..]) [0..]

>Second version, using sort and assuming that objects are rectangles

they are

Quote:
>--------------

>extent :: Ord a => [[a]] -> [(a,Int,Int,Int,Int)]
>extent =

>    groupBy (\(a,_,_) (b,_,_) -> a==b) .
>    sort .
>    concat .
>    zipWith (\i -> zipWith (\j x -> (x,i,j)) [0..]) [0..]

>I'm not sure if it's fast enough and how it can be easily made faster.

it's a gui thing, so the number of objects and the size of the input
matrix will be small.

Quote:
>I don't like these solutions much.

well, they're scalar solutions, but there's a neat vector solution
hiding in the problem.

first, flatten m to a vector:

v:,/m
v
`a `a `a `b `b `a `a `a `c `c `a `a `a `c `c `d `d `d `d `e `d `d `d `d `e

next, find the uniques:

u:?v
u
`a `b `c `d `e

next, look up each of the uniques in v:

i:v?/:u
i
0 3 8 15 19

next, decode those indices into the "base" implied by the shape of
the input matrix:

^m
5 5
s:(^m)_vs i
s
(0 0 1 3 3
0 3 3 0 4)

so now you know that the origin of the first symbol `a is 0 0, the
origin of the second symbol `b is 0 3, &c.  that is, you know the
origin coordinates of each object in the picture.

so now you've got to find the ending coordinates:

e:(^m)-(^m)_vs(|v)?/:u
e
(3 1 3 5 5
3 5 5 4 5)

that's easy, because the ending coordinates are the shape minus
the decoded indices of the uniques in the *reverse* of the vector. ;-)

so now the result is just the transpose of: the uniques and the
transpose of the starts and: the ends minus the starts:

+(u;+s,e-s)
((`a
0 0 3 3)
(`b
0 3 1 2)
(`c
1 3 2 2)
(`d
3 0 2 4)
(`e
3 4 2 1))

- Show quoted text -

Quote:

>--

> \__/              GCS/M d- s+:-- a22 C+++\$ UL++>++++\$ P+++ L++>++++\$ E-
>  ^^                  W++ N+++ o? K? w(---) O? M- V? PS-- PE++ Y? PGP+ t
>QRCZAK                  5? X- R tv-- b+>++ DI D- G+ e>++++ h! r--%>++ y-

Mon, 02 Sep 2002 03:00:00 GMT
three little problems

Quote:
> how typing

>    sequence

> produces the desired result.

main = print (sequence [[1,2,3], [4,5], [6,7,8,9]])

This complete program outputs
[[1,4,6],[1,4,7],[1,4,8],[1,4,9],[1,5,6],[1,5,7],[1,5,8],[1,5,9],[2,4,6],[2,4,7],[2,4,8],[2,4,9],[2,5,6],[2,5,7],[2,5,8],[2,5,9],[3,4,6],[3,4,7],[3,4,8],[3,4,9],[3,5,6],[3,5,7],[3,5,8],[3,5,9]]

For another application of sequence,

main = sequence (map print (sequence [[1,2,3], [4,5], [6,7,8,9]]))

prints the matrix vertically:

[1,4,6]
[1,4,7]
[1,4,8]
etc.

print is a function that takes something that can be shown as a string
and returns the IO action that will actually print it followed by
newline. map applies a function to each element of a list and returns
the list of results. So "map print (...)" is a list of IO actions,
each of them would print a single row when performed. So the first
sequence is used with the IO monad, taking a list of IO actions and
producing a single action that will execute all the prints (and collect
the results, but print returns an uninteresting result). This single
action is bound to the name "main", which must be an IO action and
is executed as the whole program.

Here both calls to sequence are used with concrete monads, but in
general sequence can be used in a function that is polymophic wrt.
the monad. For example mapM is defined as a composition of sequence
and map, and mapM_ is a variant of mapM which performs the actions
but discards their results. So as long as we are working on a level
which is independent of the particular instance of a concept, we
work polymorphically, although the type checker ensures that we are
consistent and remembers that the polymorphic type constructor we work
on must be a monad, so we get a compile error when trying to use mapM_
on something that is not a monad.

"Monad" is only an example of such a concept. A programmer may
define his own concepts (called "classes") to work abstractly over
all instances of the concept when an operation does not depend on
the details of one particular instance, yet still having benefits of
static type checking. Instances can be inferred from the result of a
function, and not only functions can be overloaded, so it's not only
the issue of static type safety.

Quote:
> >multiSort :: Ord a => [[a]] -> [Int] -> [[a]]
> >multiSort k d = transpose \$ sortBy cmp \$ transpose k
> >    where
> >    cmp    a b = uncurry compare \$ unzip \$ zipWith3 swap d a b
> >    swap 0 a b = (a,b)
> >    swap 1 a b = (b,a)

> how does this do on large lists?

n*l*log l, where n is the number of lists and l is the length of
each list, assuming that the standard library sortBy is N*log N.

List is transposed and then each column is sorted by a funny
comparison relation, which looks at d, exchanges elements of lists to
be compared that correspond to 1's in d, and compares the resulting
lists lexicographically. So it's actually n*l+l*log l when the first
list already determines the order, because those lists to be compared
lexicographically are created lazily.

--

\__/              GCS/M d- s+:-- a22 C+++\$ UL++>++++\$ P+++ L++>++++\$ E-
^^                  W++ N+++ o? K? w(---) O? M- V? PS-- PE++ Y? PGP+ t
QRCZAK                  5? X- R tv-- b+>++ DI D- G+ e>++++ h! r--%>++ y-

Mon, 02 Sep 2002 03:00:00 GMT
three little problems

hmmm - this may not actually solve my problem, and that's probably
my fault for failing to communicate it well.

multiway sort sorts columns *within* other columns, so for example,
a 0 1 0 sort sorts column 2 within column 1 within column 0.  if
multiSort does that (and not just sorting the first column up, the
second down, and the third up) then i apologize for muddying clear
waters.

Quote:

> > >multiSort :: Ord a => [[a]] -> [Int] -> [[a]]
> > >multiSort k d = transpose \$ sortBy cmp \$ transpose k
> > >    where
> > >    cmp    a b = uncurry compare \$ unzip \$ zipWith3 swap d a b
> > >    swap 0 a b = (a,b)
> > >    swap 1 a b = (b,a)

> > how does this do on large lists?

> n*l*log l, where n is the number of lists and l is the length of
> each list, assuming that the standard library sortBy is N*log N.

> List is transposed and then each column is sorted by a funny
> comparison relation, which looks at d, exchanges elements of lists to
> be compared that correspond to 1's in d, and compares the resulting
> lists lexicographically. So it's actually n*l+l*log l when the first
> list already determines the order, because those lists to be compared
> lexicographically are created lazily.

> --

>  \__/              GCS/M d- s+:-- a22 C+++\$ UL++>++++\$ P+++ L++>++++\$ E-
>   ^^                  W++ N+++ o? K? w(---) O? M- V? PS-- PE++ Y? PGP+ t
> QRCZAK                  5? X- R tv-- b+>++ DI D- G+ e>++++ h! r--%>++ y-

Mon, 02 Sep 2002 03:00:00 GMT
three little problems

Quote:
> multiway sort sorts columns *within* other columns, so for example,
> a 0 1 0 sort sorts column 2 within column 1 within column 0.

Yes. Transpose, sort columns by some relation, transpose again.
At least for your example it gives the same result.

--

\__/              GCS/M d- s+:-- a22 C+++\$ UL++>++++\$ P+++ L++>++++\$ E-
^^                  W++ N+++ o? K? w(---) O? M- V? PS-- PE++ Y? PGP+ t
QRCZAK                  5? X- R tv-- b+>++ DI D- G+ e>++++ h! r--%>++ y-

Tue, 03 Sep 2002 03:00:00 GMT

 Page 1 of 1 [ 6 post ]

Relevant Pages