On Tue, Nov 3, 2009 at 12:02 PM, Philippos Apolinarius <[email protected]> wrote: > 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 _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
