[Haskell] Queues / Lists with unbound tails

Claus Reinke claus.reinke at talk21.com
Sat May 8 17:00:23 EDT 2004

> I'm trying to write a simple fifo queue of fixed length (containing type
> Maybe a - it would be initialised to Nothings) where pushing an item pops
> the "last" item "off the end".

> However, it seems to me that there should be another solution, with a
> lazily constructed list whose tail does not yet exist.  The queue would
> consiste of the head of the list (which is the "tail" of the queue!) and a
> closure that extends the list tail (ie the queue head).
> Pushing an element would involve invoking the closure, extending the tail
> of the (lazily constructed) list, and returning another closure to
> continue the process.  The return ("pop") value would be the head of the
> list, with the next item carried forward as the next return value.

You can't really pop from a fixed-length queue. Apart from that, 
something like this?

initQ n       = foldr (.) id $ take n $ repeat (Nothing:)
pushQ front q = tail . q . (front:)
peekQ q       = (head $ q [], q)


----------- Testing:

toList q = q []

instance Show a=>Show ([Maybe a]->[Maybe a]) where
  showsPrec _ = showList . toList

x = initQ 3
xx = pushQ (Just 2) x
xxx = pushQ Nothing xx
xxxx = pushQ Nothing xxx
y = peekQ xxxx

*Main> :r
Ok, modules loaded: Main.
*Main> x
*Main> xx
[Nothing,Nothing,Just 2]
*Main> xxx
[Nothing,Just 2,Nothing]
*Main> xxxx
[Just 2,Nothing,Nothing]
*Main> y
(Just 2,[Just 2,Nothing,Nothing])

More information about the Haskell mailing list