unneeded laziness example

Serge D. Mechveliani mechvel at botik.ru
Tue Jun 12 10:57:19 EDT 2007


I wrote recently 

> And now unneeded laziness bites.
> [..]
> In  ghc-6.6,  it needs at least  100 Mb  of heap to perform.
> If I set   seq infoK'   between `shows' and `p', then it suffices 14 Mb.
> [..]
> Now: how to program real problems in Haskell ?
> Should I try to set  seq  everywhere and see whether it helps ?

I am sorry. This was false alarm.
I continued the investigation and have found that 

  Haskell and GHC are NOT guilty in this example

(uh! how good).

This is the specifics of the method.  
Probably, one needs to think of  seq  only if one applies such a method with 
expenses depending heavily on the computation order.

An interesting thing, though. The simplified and contrived example is

main = putStr $ test 18

test :: Integer -> String
test    w       =  shows (f tM) "\n"
  f           = Prelude.minimum . map Prelude.minimum
  mM          = makeMatrix w
  strictnessM = Prelude.minimum $ map Prelude.minimum mM

  tM = -- seq strictnessM $
       transpose mM

Here  mM  is  n by n  matrix of small integers,  n = 385  for  w = 18.

The program prints  f $ transpose mM.  

makeMatrix  computes the rows of  mM  in a complex way, finding  m(i,j)
uses the table of m(i',j') for other pairs (i',j'). And the time and 
space costs depend heavily on the order in which  m(i,j)  are computed.
Applying `transpose' changes (due to Haskell laziness) this order into 
more expensive one: 5 times more of heap needed. 
And adding  `seq ...'  before `transpose' returns it to initial order.
So, everything is natural.


Serge Mechveliani
mechvel at botik.ru

More information about the Glasgow-haskell-users mailing list