Re: [Caml-list] looping recursion

[Brian Hurt <bhurt@spnz.org>]

On Thu, 29 Jul 2004, james woodyatt wrote:

> On 29 Jul 2004, at 09:12, Brian Hurt wrote:
> > On Thu, 29 Jul 2004, brogoff wrote:
> >>
> >> Some problems are just way easier to solve with imperative programming
> >> though. Have you ever taken a look at purely functional catenable 
> >> deques?
> >
> > Just got added to extlib, for the record.  A simplistic version that
> > actually isn't that much more complicated than the imperitive
> > implementation.
> 
> This is extraordinary!  Do you really mean to say the deques are purely 
> functional, catenable *and* offering the same complexity as the 
> non-persistent implementation?  Which algorithm was added to extlib?
> 

The version added is O(1) ammoritized.  It has the same problem as 
quicksort and hashtables, in that on average about 1 operation in N has 
cost O(N), instead of strict O(1).

The library added was the simplest double list implementation.  Basically, 
the queue is broken into two parts- a front part and a back part, both 
kept in lists.  The back part list is kept in reverse order- so to add an 
element to the end of the queue, you prepend it to the back part list.  
You remove elements from head of the front part queue, and when it's 
empty, you replace it with the reverse of the back part list.

Every element that goes through the queue is touched precisely three 
times- once when it's added to the end of the queue, once when it's 
removed from the head of the queue, and once when we reverse the back half 
to become the new front half.  So adding and then removing N elements from 
the list costs O(N).

The core code looks like this:

type 'a deque = 'a list * 'a list

let empty = ([], []) (* the empty queue *)

let add q x =
    match q with
        | ([], []) -> (* We add the first element to the front *)
            ([x], [])
        | ([], _) -> assert false
        | (front, back) -> (front, x :: back)

let remove q =
    match q with
        | ([], []) -> invalid_arg "remove"
        | ([], _) -> assert false
        | (h :: [], back) -> h, ((List.rev back), [])
        | (h :: front, back) -> h, (front, back)

I will note that if you use a capability that applicative semantics give 
us, you can get into trouble.  Imagine the following scenario: you create 
an empty queue and add 1000 new elements.  You then remove one element.  
This does a List.rev on a 999 element list.  You then throw the modified 
queue away, and remove the first element from the original queue again, 
reversing the same 999 element list.  Repeat- every removing reverses the 
same list.

The solution to this is "don't do that!"  Note that pushing an element 
onto the head of the queue is strict O(1):

let push x (front, back) = (x :: front, back)

Rather than using the applicative semantics to undo the removal, use push 
to push back the removed elements.  This way, you only reverse the back 
half of the list once.

-- 
"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 
Brian

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners