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

[Andrew Pimlott]

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.

Simon Peyton Jones graciously offered that it is "embarrassing" that we
can't write this in Haskell, so to make him less embarrassed (and
despite my adamance on the mailing list that the implementation be
functional), I wrote an imperative version with the desired space
behavior.  Borrowing the insight that unsafePerform and unsafeInterleave
can be thought of as hooks into the evaluator, this shows more or less
what I would wish for ghc to do automatically.

    initlastST :: [a] -> ([a], a)
    initlastST xs = runST (m xs) where
      m xs = do
        r <- newSTRef undefined 
        init <- init' r xs
        last <- unsafeInterleaveST (readSTRef r)
        return (init, last)
      init' r [x]    = do writeSTRef r x
                          return []
      init' r (x:xs) = do writeSTRef r (last xs)
                          liftM (x:) (unsafeInterleaveST (init' r xs))

Andrew

[1] http://haskell.org/pipermail/haskell-cafe/2006-June/016171.html
    http://haskell.org/pipermail/haskell-cafe/2006-July/016709.html