On Sun, 25 Jul 2004, Falk Hueffner wrote:
> I think this would be a nice addition, I was looking for something
> like this just a few days ago. However, this is really a deque and
> should be called so.
I don't mind the name change. For the rest of this message I'll just
assume it happened.
> I'm wondering why the "add" function takes the new element first and
> the 't second. It seemed to me to be some kind of convention that
> functions in modules implementing some abstract data type 't the 't is
> always the first argument. This is ususally also the most useful for
> currying. I know it is similar in the standard Queue, but it already
> irritated me there :-) I'd also get rid of the synonyms, there's not
> much point for them in new code.
The signature for Queue.add is:
val add : 'a -> 'a t -> unit
As I was sort of trying for a Queue replacement, I kept the order of the
arguments the same (obviously, the unit got turned into a 'a t).
Also, I'm not sure about which is more usefull for partial function
application. Not that applying a value, the add function can become 'a ->
'a, a more usefull signature than 'a -> 'a Deque.t. Of course, how often
are you going to be adding the same element to an entire set of Deques?
I don't really have strong opinions one way or the other. I was just
> About the implementation, are you sure there is no weird sequence of
> operations that would have O(n) complexity because of frequent
> reversing? I've not looked closely, though...
If you used the immutability to "back up", you could repeatedly remove the
same element. If that element was the one that hit the O(N) complexity
step of reversing the list, you could hit a problem. The following code
demonstrates how this might work:
let myqueue =
(* make a queue of 1001 ints *)
let rec loop idx q =
let q = Deque.add idx q in
if (idx < 1000) then
loop (idx+1) q
loop 0 (Deque.empty)
let expensive () =
let rec loop idx q =
(* Remove an element from the Deque- this is always an O(N)
let q' = Deque.remove q in
if (idx < max_int) then
(* Note that by passing in q and not q' we "undo" the
loop (idx+1) q
loop 0 myqueue
We're basically using the immutability to "replay" the same O(N) removal
over and over.
Now, this is valid code, but I don't think it's reasonable code, if you
see the difference. Perhaps documenting this behavior is called for
(maybe), but I don't think it's worthwhile trying to avoid it. For this
behavior to be signifigant, you'd need all of the following things to be
1) You'd have to be using immutability to force replays of the same
removal (or small number of removals) over and over.
2) You'd need a large number of items in the queue (reversing a list of 3
items isn't that expensive).
3) You'd need to be replaying the same removal many times (reversing even
a long list once or twice unnecessarily isn't that painfull)
4) The removal you are replaying needs to be the O(N) one.
If any of these factors aren't the case, it's not a problem. And I'd
argue that all of them are exceptional- that in the common case, replays
are rare to non-existant, the queue only holds a small number of items at
any given time, that in the case where replays do happen, they happen to a
"safe" (O(1)) removal, and that only a finite number of replays (1-2) will
There are tricks to speed up the rare case. Basically you keep the first
O(log N) and last O(log N) elements in lists, and the rest of the elements
in a tree. You can then lazily add and remove O(log N) elements at a shot
from the tree (which you can finesse to only take O(log N) time to handle
all O(log N) elements), meaning that instead of O(N) worst case cost, it's
O(log N). However, this approach signifigantly slows down the common
Are we willing to slow down the common case to speed up the exceedingly
"Usenet is like a herd of performing elephants with diarrhea -- massive,
difficult to redirect, awe-inspiring, entertaining, and a source of
mind-boggling amounts of excrement when you least expect it."
- Gene Spafford