Space complexity of head.reverse vs. last

haskell, space-complexity

Solution

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 _      _     = []

Problem

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.

Original source