Re: [Caml-list] Wanted - General Purpose "Glue Logic" Data-Structures

[Brian Hurt <brian.hurt@qlogic.com>]

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