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

[Caml-list] Wanted - General Purpose "Glue Logic" Data-Structures
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2003-03-20 (16:42) From: Brian Hurt Subject: Re: [Caml-list] Wanted - General Purpose "Glue Logic" Data-Structures
```On Wed, 19 Mar 2003, John Gerard Malecki wrote:

> The program broke down in 2 places.  First, List.concat was used to
> convert the output of the fracturer from 'a list list to 'a list.  Not
> only is List.concat not tail-recursive but @ (Pervasives.append) is
> also not tail-recursive.  I modified the fracturer to directly produce
> 'a list.

I have a tail-recursive version of the entire list library, including
append, kicking around- I'll send it to you.  That fixes this problem.
But thank you for proving me right- this *is* a problem :-).

As for producing the tree, I'd recommend using a self-balancing tree-
perhaps a Red-Black tree (which is surprisingly easy to implement in
Ocaml.  It's annoying that the standard library's set doesn't *quite* do
what you need).  Inserting an element should be O(log n), meaning you
should be able to build the whole tree in O(n * log n).

Hmm.  Alternatively, you might also look at my Priority Search Queue
implementation.  This probably does more than you need, but that's better
than doing less than you need :-).  With PSQueue:

>    - fast computation of cardinality

Cardinality is, or should be, O(1) (if all else, I just keep a running
count of elements in the tree).

>
>    - fast addition of single elements

PSQueue is O(log n) addition.

>
>    - fast addition of lists of elements

Adding a list of k elements to a n-element PSQueue is O(k * log n).

>
>    - fast removal of single elements in random order

PSQueue is O(log n) removal of any element.  Also, finding any given
element given it's key is O(log n).

>
>    - not choking on a large data size

PSQueue is not tail recursive, but it only uses O(log n) stack space (it's
a balanced tree).  I'll send the code on and you can look at it.

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

```