Space complexity of head.reverse vs. last

Question

In many systems, head.reverse requires space proportional to the size of the list, whereas last requires constant space.

Are there systems to perform such a transformation? Similarly for reverse.take n.reverse?

Edit: I would like to extend my question: I am not after a concrete transformation — I am rather after any optimization to this end.

Answer 1

You can transform reverse . take n . reverse by treating your list as a particularly obtuse lazy natural number: empty lists are zero, and conses are succ. For lazy naturals encoded as lists, subtraction is drop:

type LazyNat a = [a]

lengthLazy :: [a] -> LazyNat a
lengthLazy = id

dropLazy :: LazyNat a -> [b] -> [b]
dropLazy [] xs = xs
dropLazy (_:n) (_:xs) = dropLazy n xs
dropLazy _ _ = []

-- like Prelude.subtract, this is flip (-)
subtractLazy :: Int -> LazyNat a -> LazyNat a
subtractLazy = drop

Now we can easily implement the "take last n" function:

takeLast n xs = dropLazy (subtractLazy n (lengthLazy xs)) xs

...and you'll be pleased to know that only n conses need to be in memory at any given time. In particular, takeLast 1 (or indeed takeLast N for any literal N) can run in constant memory. You can verify this by comparing what happens when you run takeLast 5 [1..] with what happens when you run (reverse . take 5 . reverse) [1..] in ghci.

Of course, I've tried to use very suggestive names above, but in a real implementation you might inline all the nonsense above:

takeLast n xs = go xs (drop n xs) where
    go lastn  []    = lastn
    go (_:xs) (_:n) = go xs n
    go _      _     = []

Answer 2

You can write a simple rewrite rule for this.

http://www.haskell.org/haskellwiki/Playing_by_the_rules

Fusion rules may catch it, too, depending how reverse is encoded.