[Haskell] Queues / Lists with unbound tails
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)
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
Ok, modules loaded: Main.
(Just 2,[Just 2,Nothing,Nothing])
More information about the Haskell