[Haskell-cafe] Gauss Elimination -> More Clean2Haskell
Ryan Ingram
ryani.spam at gmail.com
Tue Nov 3 15:30:48 EST 2009
On Tue, Nov 3, 2009 at 12:02 PM, Philippos Apolinarius
<phi500ac at yahoo.ca> 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
More information about the Haskell-Cafe
mailing list