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