[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)

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)

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

Brandon
-------------- next part --------------
A non-text attachment was scrubbed...
Name: a.out.ps
Type: application/postscript
Size: 20647 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20060927/79ab0e88/a.out.ps