[Haskell] Random matrices

[Udo Stenzel]

Scherrer, Chad wrote:
> I keep getting stack overflows, so I think my code must be too lazy somewhere
> (that's what that means, right?)

Most often, yes.  Afaict, the best way to spot these leaks is to
simulate lazy evaluation in your head.  After fumbling with ghc's heap
profiling facilities and getting nothing usable out of it, I don't see a
better way anyway.

In the case of your code, to get at the result, most elements of the
matrix don't need to be known.  They are not evaluated when building the
matrix!  Due to the implicit state they depend on each other, however.
So only when you demand part of the result, is any intermediate state
evaluated at all.

The most elegant way to cure your problem would be a strict state monad.
Unfortunately, there is no such thing (apart from Control.Monad.ST,
which is quite a bit different), you'd have to implement it yourself,
which makes this a silly suggestion.  Also, I'm afraid, a StdGen cannot
be forced easily; it seems to contain some lazyness in its bowels.  I
had no luck when I tried this route.

Something else is possible, though.  Forcing the random numbers in turn
forces the state.  So demand for the arrays must be propagated into
demand for their elements.  randomArray is the right spot to do this.

Simplifying your randomArray a bit, we now use a strict variant of
sequence, and everything works (though it is still dog slow in GHCi).

> randomArray n x = liftM (listArray (1,n)) . sequence' . replicate n
>
> sequence' [] = return []
> sequence' (mx:mxs) = do x  <- mx
>                         xs <- sequence' mxs
>                         x `seq` return (x:xs)

[...]


> tester n = fst $ runState vals $ mkStdGen 1
>     where vals = sequence' . repeat $ randomMatrix n n

tester has the same problem, though diminished by a factor of 100.
Putting a strict sequence here helps again, cutting back on heap usage.
The optimized binary now runs in under 2MiB of memory.

Interestingly, using an unboxed array has almost the same effect.  This
failed, because Matrix couldn't use an unboxed array as well.


Udo.
-- 
"You see, wire telegraph is a kind of a very, very long cat.  You pull his
tail in New York and his head is meowing in Los Angeles.  Do you understand
this?  And radio operates exactly the same way: you send signals here, they
receive them there.  The only difference is that there is no cat."
	-- Albert Einstein, when asked to describe radio
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://www.haskell.org//pipermail/haskell/attachments/20050823/c30c2f1c/attachment.bin