Space leak only in certain cases in GHC interpreter when doing: concat <some list> !! n

Question

I define my own version of concat, myConcat:

module Eh where  myConcat []          = [] myConcat ([]:os)     = myConcat os myConcat ((x:xs):os) = x : myConcat (xs:os)  (!!!)  :: [a] -> Int -> a xs     !!! n | n < 0 = error "negative index" []     !!! _         = error "index too large" (x:_)  !!! 0         = x (_:xs) !!! n         = xs !!! (n-1) 

If I do myConcat <some huge list> !! n in the GHC interpreter, it steals my memory at 300MB/s, and I have to kill it before it can summon the OOM killer. Note here that I load Eh as "interpreted", I don't compile it before loading it.

 code run in the GHC interpreter        space leak? myConcat (repeat [1,2,3,4]) !! (10^8)  Yes concat (repeat [1,2,3,4]) !! (10^8)    No myConcat (repeat [1,2,3,4]) !!! (10^8) No concat (repeat [1,2,3,4]) !!! (10^8)   No 

Now if I compile Eh (ghc --make -O2 Eh.hs), and then load it in the interpreter and re-run these tests, none of them space leak. Same if I compile each test case instead of running them in the interpreter.

What's going on?

---

I'm running GHC 6.12.3.

Answer 1

The issue here is strictness. Evaluation in Haskell is non-strict, so computations are usually performed only if their results are really needed. Instead, a so-called thunk is created that represents the not-yet-performed computation.

In certain cases the compiler can however detect that the result of the computation will be needed anyway and therefore replaces the creation of thunks by the actual computation.

The Haskell Wiki probably explains this better.

To fix your myConcat function you have to make sure it doesn't create millions of thunks by manually forcing strict evaluation. One (not very pretty looking) way of doing this could be:

myConcat []          = [] myConcat ([]:os)     = myConcat os myConcat ((x:xs):os) = ((:) $! x) myConcat (xs:os)