Re: [Caml-list] Priority queues, reloaded

[james woodyatt <jhw@conjury.org>]

"Jon Harrop" <jon@ffconsultancy.com> asks about heaps and priority queues in Ocaml:
> 
> Anyone got this in OCaml?

I released this years ago.  It's stable, meaning I use it all the time, and I never touch it.

   <https://bitbucket.org/jhw/oni>

From the README in the Cf library:

>> Highlighted features include:
>> 
>> - Functional streams and stream processors (extended).
>> - Functional bootstrapped skew-binomial heap.
     *******************************************
>> - Functional red-black binary tree (associative array).
>> - Functional sets based on red-black binary tree.
>> - Functional real-time catenable deque.
>> - Functional LL(x) parsing using state-exception monad.
>> - Functional lazy deterministic finite automaton (DFA).
>> - Functional lexical analyzer (using lazy DFA and monadic parser).
>> - Functional substring list manipulation (message buffer chains).
>> - Gregorian calendar date manipulation.
>> - Standard time manipulation.
>> - System time in Temps Atomique International (TAI).
>> - Unicode transcoding.
>> - Universal resource identifier (URI) manipulation.
>> - Extended socket interface (supports more options, and UDP w/multicast).
>> - I/O event multiplexing (with Unix.select).
>> - Functional XML stream parsing and generation
>> - Functional MIME stream parsing and generation

Among other treasures, it has priority queues built with the bootstrapped skew-binomial heaps.

  <https://bitbucket.org/jhw/oni/src/ef09a44a61ea/cf/cf_pqueue.mli>
  <https://bitbucket.org/jhw/oni/src/ef09a44a61ea/cf/cf_sbheap.mli>

Nobody knows about my Oni project because I rarely put any effort into promoting it, but its Cf library is an excellent alternative to the OCaml standard library in many ways.  There is a GODI package for it, of course, but the OCaml With Batteries people settled on a more popular alternative (and who can blame them) so again nobody knows about it.  Nevertheless, if you need the complete array of functional data structures in OCaml, you should look at the Cf library I wrote.  It's pretty good.


—
j h woodyatt <jhw@conjury.org>
http://jhw.dreamwidth.org/