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

[Brandon Moore]

Andrew Pimlott wrote:

This is a follow-up to a thread from June-July[1].  The question was how to
write the function

    initlast :: [a] -> ([a], a)
    initlast xs = (init xs, last xs)

so that it can be consumed in fixed space:

    main = print $ case initlast [0..1000000000] of
                     (init, last) -> (length init, last)

Attempts were along the lines of

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

I seemed obvious to me at first (and for a long while) that ghc should
force both computations in parallel; but finally at the hackathon
(thanks to Simon Marlow) I realized I was expecting magic:  The elements
of the pair are simply independent thunks, and there's no way to "partly
force" the second (ie, last) without forcing it all the way.

According to the stuff about "selector thunks", it seems this should work

initlast [x] = ([],[x])
initlast (x:xs) =
let ~(init,last) = initlast xs
in (x:init, last)



main = print $ case initlast [0..100000000]
of (init, last) -> (length init, last)

Brandon

It does, at least when I build with -ddump-simpl. Other builds, I get a program that overflows. Attached is a heap profile for a run with the main (10M rather than 100M as above - that just takes too long)

a.out.ps
Description: PostScript document

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe