On Tue, Nov 3, 2009 at 12:02 PM, Philippos Apolinarius
1 --- The program must be implemented using arrays. Update must be done in place, in order to minimize use of the garbage collector. I have used Data.Array.IO, but I guess that Data.Array.ST is better. Is it easy to rewrite the program in order to use DataArray.ST?
It should be pretty easy as long as the rest is pure; ST is a subset of I/O that deals with algorithms that have mutable variables/arrays but no observable side-effects. ST safely guarantees that no side-effects escape to somewhere they can be observed through a clever type-system trick.
2 -- I liked very much the forM_ monad. I wonder if there is an accumulating monad that play the role of a program like leftSide.
forM_ is just a function; it works for all monads. Probably just a terminology error?
3 -- Clean program almost double its speed, if one uses strictness annotations. Is it possible to use similar anotations for Haskell?
Yes. The common ways to do this are to use ! annotations in data structures, like so: ] data Foo s = Foo !Int !Int !(STArray s (Int,Int) Double) You also can use seq and/or $! to guide the evaluation order of your expressions: x <- readArray a (1,1) writeArray a (1,1) $! (x+1) -- forces x+1 to evaluate instead of writing a thunk. If you really care about speed, you probably want to look into STUArrays; these store unboxed values and should be about as fast as a C array. Now to the stylistic comments: You can use guards better to not repeat yourself so often:
prtSol i n1 arr | i < 1= return () prtSol i n1 arr= do b <- readArray arr (i, n1) putStr ((show b)++" ") prtSol (i-1) n1 arr
becomes ] prtSol i n1 arr ] | i < 1 = return () ] | otherwise = do ] b <- readArray arr (i, n1) ] putStr ((show b)++" ") ] prtSol (i-1) n1 arr Similarily:
fillArray xs s (i, n) (j, m) arr | i > n= return () fillArray xs s (i,n) (j, m) arr | i==n && j>m= do
this branch doesn't need "do" because writeArray returns ()
writeArray arr (i, j) s return () fillArray xs s (i, n) (j, m) arr | j > m = do writeArray arr (i, j) s fillArray xs 0.0 (i+1, n) (1, m) arr fillArray (val:xs) s (i, n) (j, m) arr= do writeArray arr (i, j) val fillArray xs (s+val) (i, n) (j+1, m) arr
] fillArray xs s (i, n) (j, m) arr ] | i > n= return () ] | i==n && j>m = writeArray arr (i, j) s ] | j > m = do ] writeArray arr (i, j) s ] fillArray xs 0.0 (i+1, n) (1, m) arr ] | otherwise = do ] writeArray arr (i, j) val ] fillArray xs (s+val) (i, n) (j+1, m) arr I'll let someone else show you how to build this into a fold. -- ryan