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
|