[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