Re: [Ocaml-lib-devel] De-functor-ized Psqueue

[Brian H. <bri...@ql...>]

On Mon, 26 May 2003, Nicolas Cannasse wrote:

> > Also todo: to_enum, of_enum, to_stream, and of_stream should be added.
> > The to_* should be both by priority and by key.
> 
> Even if I like Streams I think that enums are somehow much powerful and less
> error prone (since you can't do next() ). 

The more I think about this, the more I disagree.  Case in point: consider 
taking a list of items and turning it into a balanced tree.  Using the 
standard list operations, this is not too horribly ugly:


type 'a tree_t = Void
               | Node of 'a tree_t * 'a * 'a tree_t

let tree_from_lst lst =
    let rec subtree lst len =
        if (len > 1) then
            let pivot = len/2 in
            let left, lst' = subtree lst pivot in
            match lst' with
                h :: t -> 
                    let right, t' = subtree t (len - pivot - 1) in
                    Node(left, h, right), t'
                | _ -> assert false
        else if (len > 0) then
            match lst with
                h :: t -> Node(Void, h, Void), t
                | _ -> assert false
        else
            Void, lst
    in
    let len = List.length lst in
    if (len > 0) then
        let tree, _ = subtree lst (List.length lst) in
        tree
    else
        Void

Now consider rewritting this to take an Enum instead of a list.  You have 
to force the algorithm into fold somehow- which means managing a 
handrolled stack (the above code is double non-tail recursive).  
Signifigantly uglier.

On the other hand, using a stream is almost as bad, as you need a way to 
find out the number of elements in the stream before starting (above done 
with a call to String.length).

The above code, or rather code much like it, showed up in some exploratory 
code I was doing to implement a interval map (see the thread in the main 
list).  The idea being that a tree would make inserts and removals O(log 
N), while I could do (for example) unions by first converting both trees 
to a list, unioning the lists, and recreating the tree from the unioned 
list, list:

let union a b =
    let rec loop alst blst accum =
        match alst, blst with
           (amin, amax):: atail, (bmin, bmax)::btail ->
               if (amax < bmin) then
                   loop atail blst ((amin, amax) :: accum)
               else if (bmax < amin) then
                   loop alst btail ((bmin, bmax) :: accum)
               else
                   loop atail btail (((min amin bmin), (max amax bmax))
                                      :: accum)
            | _, [] -> List.rev_append accum alst
            | [], _ -> List.rev_append accum blst
            | [], [] -> List.rev accum
    in
    let alist = list_from_tree a
    and blist = list_from_tree b
    in
    tree_from_list (loop alist blist)
;;

But this requires me to instantiate both lists completely- requiring O(N) 
memory overhead to complete.  If I could "virtualize" the construction of 
the lists as an enumeration or stream, I could reduce the memory 
requirements to O(log N).  It's not hard to force list_from_tree into an 
enumeration.  I need to fake a stack, but in this case it's cleaner- all I 
need for a stack is the list of nodes I need to go down the left hand 
side of.  But forcing tree_from_list into Enum.map is neither simpler
than the above code, nor less error prone.  Signifigantly more complicated 
and error prone, I would think.

> Adding Stream support to psqueue
> would imply adding it for other data structures as well ( since we went to
> make things consistent ).
> I would prefer an  Enum.stream / Enum.of_stream and keep only "enum" usage
> into data structures.

The more I think about, the more I think the solution is to merge Stream 
and Enum, and create a best-of-breed interface (probably called 
ExtStream).  IMHO, this api would:
	- have an exported next, like Stream
	- have an exported count, like Enum
	- have the usual gang of suspects- map, iter, fold, etc.
	- next returns 'a option, with None meaning no more elements,
	  like Stream, instead of returning 'a and throwing an exception
	  on no more elements.

For the last one, fold (for example) currently looks like:
let fold f init t =
        let ret = ref init in
        let rec loop accu =
                loop (f (try t.next() with No_more_elements as e -> ret := 
accu; raise e) accu)
        in
        try
                loop init
        with
                No_more_elements -> !ret

If next returns 'a option instead of 'a, we could rewrite it like:

let fold f init t =
    let rec loop accu =
        match t.next() with
            None -> accu
            | Some x -> loop (f x accu)
    in
    loop init

For sheer code clarity, I think 'a option is a cleaner response than 
throwing an exception.

Brian