Re: [Haskell-cafe] Computing lazy and strict list operations at the same time

14 Jul 2006

      On Mon, Jun 19, 2006 at 05:50:13PM +0100, Duncan Coutts wrote:
...
On Mon, 2006-06-19 at 17:03 +0100, Jon Fairbairn wrote:
...
il [] = error "foo"
il [x] = ([], x)
il (x:xs) = cof x (il xs)
            where cof x ~(a,b) = (x:a, b)
--                      !
From a quick test, it looks like none of our suggested solutions
actually work in constant space.
main = interact $ \s ->
  case il s of
    (xs, x) -> let l = length xs
               in l `seq` show (l,x)
I was hoping to have enlightenment served to me, but since nobody has
explained this, I took a crack at it.  I still can't explain it, but I
got some data that maybe somebody else will understand.  My code:

    initlast :: [a] -> ([a], a)
    initlast [x]    = ([], x)
    initlast (x:xs) = let (init, last) = initlast xs
                      in  (x:init, {-# SCC "last" #-} last)

    lenshow n (_:xs) last = let n1 = n+1 in n1 `seq` lenshow n1 xs last
    lenshow n [] last = show (n,last)

    main = interact $ \s -> case initlast s of
      (xs, x) -> lenshow 0 xs x 

lenshow is just "show (length xs, x)", written out so I can tweak it
later.  This exhibits the runaway space usage with a large input that
Duncan described.  If you throw away "last" in lenshow and just "show
n", it runs in constant space.

It seems that the reference to "last" that I annotated as a cost center
is holding a chain of trivial thunks--trivial because "last" is just
being copied from the result of the recursive call to initlast.  I
thought maybe I could get rid of them by returning an unboxed tuple from
initlast, but this turned out to make no difference.

Profiling gave a couple hints.  Retainer set profiling (-hr) showed the
retainer set holding all the memory was

    {}

I think this confirms that last holding a chain of thunks.  I'm still
surprised that ghc doesn't see that they're trivial.  It feels like it
should be an easy optimization.

Constructor and type profiling (-hd and -hy) both show the memory held
by stg_ap_1_upd_info.  I don't know what that means.

Most frustrating, I can't find any work around:  No matter how I tried
to write initlast, it had the same leak when consumed this way.  (NB:
functional implementations only need apply.)  Granted, I can't think of
any good reason to code in this style, but it's hard for me to accept
that it should be impossible.

Finally, here is a (silly) version that doesn't leak:

    initlast :: [a] -> ([a], [a])
    initlast [x]    = ([], [x])
    initlast (x:xs) = let (init, last) = initlast xs
                      in  (x:init, undefined:last)

    lenshow n (_:xs) (_:ls) = let n1 = n+1 in n1 `seq` lenshow n1 xs ls
    lenshow n [] [last] = show (n,last)

This is the first case I recall in which adding more constructors makes
a space leak go away, because it gives me something to force (vis
"_:ls).  With the original implementation, there was no way to "partly
force" last, one thunk at a time.  Have others used this technique?

Andrew

Re: [Haskell-cafe] Computing lazy and strict list operations at the same time

Andrew Pimlott