This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

[Caml-list] looping recursion
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: -- (:) From: Brian Hurt Subject: Re: [Caml-list] looping recursion
```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 *)

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

```