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

Sometimes it does compile to a program that runs in constant space, 
sometimes it doesn't!

I've sent a message to the list with a heap profile of a run on 10M 
numbers, but it's being held for moderation because it's too big.

Brandon