Queues / Lists with unbound tails
Hi, 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". data Queue a = QUEUE (Maybe a -> (Queue a, Maybe a)) queue :: Maybe a -> Queue a queue n1 = QUEUE (\n2 -> (queue n2, n1)) consQ :: Queue a -> Queue a -> Queue a consQ (QUEUE q1) (QUEUE q2) = QUEUE (\n -> let (q1', n1) = q1 n (q2', n2) = q2 n1 in (consQ q1' q2', n2)) works, and lets me construct arbitrary length queues, but the push/pop operation is O(n) (I believe) in the length of the queue. I don't have Okasaki's book with me, but I'm pretty sure he gives a solution that has two lists, with the second inverted via an operation that is either amortized O(1), or inverted stepwise using lazy evaluation. 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. I think this would be simple to implement in Prolog or Oz, for example, where the last element of a list can be unbound. I assume the same is possible in Haskell using laziness and closures. However, I cannot nail it down. Can anyone help? Apologies for the unclear description. If I could describe the solution clearly then I could write the code and wouldn't need to ask :o) Thanks, 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
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) Cheers, Claus ----------- 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 [Nothing,Nothing,Nothing] *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])
Claus Reinke said: [...]
something like this?
initQ n = foldr (.) id $ take n $ repeat (Nothing:) pushQ front q = tail . q . (front:) peekQ q = (head $ q [], q)
Yes, thanks. At least, it looks easy to get what I want from that. Sigh. It seems so obvious now. When will this fucntional programming / laziness deal finally become completely clear? 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
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
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".
well, tail gets a complete list whenever the back of the queue is inspected. And since tail doesn't actually care about anything but the first (:) in a list, it could easily be applied to a list containing (relatively) free variables deeper inside: (\x->tail (_:x)) --> (\x->x). It's only that Haskell implementations have tended to shy away from terms with relatively free variables.. So, unfortunately, naive implementations will not share the evaluation of the tail applications between inspections of the back of the queue and the construction of the new queue. That's why I recommended performance testing, as we don't have enough information for complexity arguments. You said you only wanted to use queues via a single combined operation: shiftQ front q = let q' = \rest->q (front: rest) in (head (q' []), \rest-> tail (q' rest) ) using Integer instead of Maybe Integer (and modulo all kinds of errors;-), assuming demand for the head (back end), and a suitable operational semantics of Haskell (..), we get something like this reduction sequence: shiftQ 1 ( (0:) . (0:) . (0:) ) -> let q' = \rest-> ( (0:) . (0:) . (0:) ) (1: rest) in (head (q' []), \rest-> tail (q' rest) ) -> (1) {here we copy q', even though there are further reductions in the function body that could be shared, including tail applications in shifted queues..} let q' = \rest-> ( (0:) . (0:) . (0:) ) (1: rest) in (head (\rest-> ( (0:) . (0:) . (0:) ) (1: rest) []) ,\rest-> tail (q' rest) ) -> let q' = \rest-> ( (0:) . (0:) . (0:) ) (1: rest) in (head ( ( (0:) . (0:) . (0:) ) (1: []) ) ,\rest-> tail (q' rest) ) -> let q' = \rest-> ( (0:) . (0:) . (0:) ) (1: rest) in (head ( (0:) ( ( (0:) . (0:) ) (1: []) ) ) ,\rest-> tail (q' rest) ) -> let q' = \rest-> ( (0:) . (0:) . (0:) ) (1: rest) in (head ( 0: ( ( (0:) . (0:) ) (1: []) ) ) ,\rest-> tail (q' rest) ) -> (2) {all reductions between (1) and (2) are parametric in rest, so could have been shared..} let q' = \rest-> ( (0:) . (0:) . (0:) ) (1: rest) in (0, \rest-> tail (q' rest) ) = (0, \rest-> tail ((\rest->((0:).(0:).(0:)) (front:rest)) rest) ) The new queue in the snd part of the result still has the tail application, so, as you point out, these will pile up for successive shiftQs (it would be quite possible to share the evaluation of tail, before substituting for q', but I don't think any current Haskell implementation is doing that). GHC does some full-lazyness stuff, but I doubt that will solve the issue ("full" lazyness does not mean optimal number of reductions..). Another way to share the tail reductions would be by forcing them before returning the new queue: (0, \rest-> tail ((\rest->((0:).(0:).(0:)) (front:rest)) rest) ) -> (0, \rest-> tail ( ((0:).(0:).(0:)) (front:rest)) ) -> (0, \rest-> tail ( (0:) ( ((0:).(0:)) (front:rest) ) ) ) -> (0, \rest-> tail ( 0: ( ((0:).(0:)) (front:rest) ) ) ) -> (0, \rest-> ( ((0:).(0:)) (front:rest) ) ) Such a "strict" abstraction (that evaluates its body to whnf) would often be useful, but again, I don't think it is supported.
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).
the type of queue's here is [a]->[a], but with the implicit constraint that the lenght of the partial list inside remains constant. tail is _composed_ with such queues and some (front:), to keep that invariant. tail is _applied_ to perfectly normal lists, as far as the definition of tail is concerned (which will only inspect the top (:) of the list). Cheers, Claus
shiftQ front q = let q' = q . (front:) in (head (q' []), trace "tail" . tail . q' )
the problem with this was that new queues get constructed under lambda-abstractions (binding the not yet available input), but current Haskell implementations do not reduce under lambdas. the reductions involved in those constructions are thus repeated every time the queue is shifted/inspected (the trace shows the repeated applications of the nested tail operations in a sequence of shiftQs). [[from the "don't try this at home" (nor anywhere else) category:-]] if we're certain that our queue will be used single-threadedly, we can get around this limitation using single-read variables. first, here's a way to "open" an abstraction without applying it to a concrete argument - we just apply it to a hole which we promise to fill with an argument later on. openFct f returns both the body of f (possibly with holes) and a variant of f that will fill the holes and reuse the body: {-# NOINLINE openFct #-} openFct f = unsafePerformIO $ do mv <- newEmptyMVar let arg = unsafePerformIO $ takeMVar mv body = f arg return ( body , \arg->unsafePerformIO $ do putMVar mv arg return body) using this, we can modify shiftQ - we can't apply a queue twice anymore, but we know that q' is non-empty, so the back end of q' does not depend on the missing front end, and we can use head on the open body of q: shiftQ'' front q = let (body,q') = openFct $ q . (front:) in (head body,trace "tail" . tail . q') this way, the evaluation of the construction operations is shared (as the trace confirms). just in case you hadn't noticed ;-) this construction is "unsafe"! in particular, once we've opened an abstraction, we should only apply it once. here's an example of what can happen otherwise: Prelude Main> let (_,f) = openFct tail Prelude Main> f "hihi" "ihi" Prelude Main> f "hoho" "ihi" Prelude Main> f "huhu" "*** Exception: thread blocked indefinitely cheers, claus ps. using tryPutMVar would be a bit nicer, but still problematic.
On Sat, 8 May 2004, andrew cooke wrote:
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".
data Queue a = QUEUE (Maybe a -> (Queue a, Maybe a))
queue :: Maybe a -> Queue a queue n1 = QUEUE (\n2 -> (queue n2, n1))
I suppose, push/pop in this implementation is just function application. so if q :: Queue a I can write: (q', top) = q new_elem q' and q have the same length.
consQ :: Queue a -> Queue a -> Queue a consQ (QUEUE q1) (QUEUE q2) = QUEUE (\n -> let (q1', n1) = q1 n (q2', n2) = q2 n1 in (consQ q1' q2', n2))
works, and lets me construct arbitrary length queues, but the push/pop operation is O(n) (I believe) in the length of the queue.
I don't have Okasaki's book with me, but I'm pretty sure he gives a solution that has two lists, with the second inverted via an operation that is either amortized O(1), or inverted stepwise using lazy evaluation.
Source and explanation of those algorithms are part of my Dessy project: http://www.stud.tu-ilmenau.de/~robertw/dessy/fun/Queue.hs The two-list solution is also the only purely functional way to achieve this efficiency for Queues. The solution that "opens the closures" is imperative in essence (and probably better implemented in an imperative language). Robert
participants (3)
-
andrew cooke -
Claus Reinke -
Robert Will