Space leak? Was: [Haskell] Queues / Lists with unbound tails

[andrew cooke]

Claus Reinke said:
> initQ n       = foldr (.) id $ take n $ repeat (Nothing:)
> pushQ front q = tail . q . (front:)

Why doesn't repeated pushing give a space leak?  As far as I can see, tail
never gets a "complete" list on which it can act, so repeated pushing will
construct a function with more and more "tails" at the "front" and more
and more "fronts" at the "tail".

Maybe I'm being mislead by the types?  My reasoning is that tail has type
[a] -> [a], but is applied to something that is never type [a], but rather
type [a] -> [a].  Is that rubbish?  Is it wrong to think of [a] -> [a] as
a single thing (the first "[a]" is what is being pushed on the queue, not
the queue itself, so it's not OK to simply treat is as a suitable argument
for tail to operate on).

I did try to measure this this morning, before coming to work, but the
results were inconclusive (I need to read the GHC manual to see what help
it gives for this and try again - looking at memory usage in Window's task
manager showed no significant change in memory use, even if I dropped
"tail" completely from the code).

Cheers,
Andrew

-- 
` __ _ __ ___  ___| |_____   work web site: http://www.ctio.noao.edu/~andrew
 / _` / _/ _ \/ _ \ / / -_)  personal web site: http://www.acooke.org/andrew
 \__,_\__\___/\___/_\_\___|  list: http://www.acooke.org/andrew/compute.html