Author 
Message 
stevan apte #1 / 6

three little problems
here are three little realworld problems which cropped up in my work over the last week. the k solutions are exactly as they appear in the production code. 1. crossproduct 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,es)} 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 


Marcin 'Qrczak' Kowalcz #2 / 6

three little problems
Quote: > here are three little realworld problems which cropped up in my > work over the last week.
As usual, I will answer with Haskell. Quote: > 1. crossproduct 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] It works for any monad m. Monad  so wonderful concept! 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,ki+1,lj+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 


stevan apte #3 / 6

three little problems
Quote:
>> here are three little realworld problems which cropped up in my >> work over the last week. >As usual, I will answer with Haskell.
why do i get the impression that you like haskell? Quote: >> 1. crossproduct 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] >It works for any monad m. Monad  so wonderful concept! >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 produces the desired result. perhaps you can show more of 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? 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,ki+1,lj+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,es) ((`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)) 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 


Marcin 'Qrczak' Kowalcz #4 / 6

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 


stevan apte #5 / 6

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 


Marcin 'Qrczak' Kowalcz #6 / 6

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 


