On Jun 19, 2006, at 12:50 PM, Duncan Coutts wrote:
On Mon, 2006-06-19 at 17:03 +0100, Jon Fairbairn wrote:
On 2006-06-19 at 15:24-0000 "C Rodrigues" wrote:
Here's a puzzle I haven't been able to solve. Is it possible to write the initlast function?
There are functions "init" and "last" that take constant stack space and traverse the list at most once. You can think of traversing the list as deconstructing all the (:) [] constructors in list.
init (x:xs) = init' x xs where init' x (y:ys) = x:init' y ys init' _ [] = []
last (x:xs) = last' x xs where last' _ (y:ys) = last' y ys last' x [] = x
Now, is there a way to write initlast :: [a] -> ([a], a) that returns the result of init and the result of last, takes constant stack space, and traverses the list only once? Calling reverse traverses the list again. I couldn't think of a way to do it, but I couldn't figure out why it would be impossible.
il [] = error "foo" il [x] = ([], x) il (x:xs) = cof x (il xs) where cof x ~(a,b) = (x:a, b) -- !
From a quick test, it looks like none of our suggested solutions actually work in constant space.
main = interact $ \s -> case il s of (xs, x) -> let l = length xs in l `seq` show (l,x)
using ghc: ghc -O foo.hs -o foo ./foo +RTS -M10m -RTS < 50mb.data
using runhugs: runhugs foo.hs < 50mb.data
in both cases and for each of the three solutions we've suggested the prog runs out of heap space where the spec asked for constant heap use.
Actually, the OP asked for constant stack space, which is quite different and much easier to achieve.
So what's wrong? In my test I was trying to follow my advice that we should consume the init before consuming the last element. Was that wrong? Is there another way of consuming the result of initlast that will work in constant space?
That is, nonetheless, an interesting question.
Note that by changing discarding the x we do get constant space use: main = interact $ \s -> case il s of (xs, x) -> let l = length xs in l `seq` show l -- rather than 'show (l,x)'
Why does holding onto 'x' retain 'xs' (or the initial input or some other structure with linear space use)?
Duncan
Rob Dockins Speak softly and drive a Sherman tank. Laugh hard; it's a long way to the bank. -- TMBG