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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
