ocaml-lib-devel — Developer's mailing list

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

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

On Tue, 27 May 2003, Nicolas Cannasse wrote:

> > 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).
> 
> Since you're building a tree you don't need to be tail rec ( the stack will
> grow in O(log n) ! )

Yeah.  Building a stack isn't the problem- in fact, I have to do that for 
tree_to_enum.  It's the complexity of the stack.  

> 
> > For sheer code clarity, I think 'a option is a cleaner response than
> > throwing an exception.
> 
> I don't agree here :
> - BUT the internal next is most of the time "concatening" the next functions
> in a purely functional way, so for example after two Enum.maps and doing an
> Enum.iter, you'll have to check the None/Some three times ! 

For Enum.iter this is correct.  However, for doing just about anything 
else you need to try/catch the exception the same number of times you need 
to check for None/Some.  And I would expect map and fold to be at least as 
important as iter.

In both cases the expected case is for it not to be the end of the 
enumeration- for the exception not to be thrown, or for Some x to be 
returned.  I don't know how expensive setting up a try/catch block is, but 
since the branch between None/Some is a highly predictable branch, the 
cost of the branch is 1 clock cycle *or less*.  Add another clock cycle 
for the memory load (from L1 cache- the word was just allocated and 
filled).  Below the level that would be measurable in any real-world case, 
would be my guess.  In either case, I think this is a premature 
optimization.

Plus there is the problem of having the exported next behaving differently 
from the imported next- a likely source of confusion.

Brian

Re: [Ocaml-lib-devel] Enum.iter2

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

On Tue, 27 May 2003, Nicolas Cannasse wrote:

> > Is there a reason why Enum.iter2 does index stuff?
> 
> Certainly a too fast copy/fast from Enum.iter2i  , not mine but it's been
> properly fixed.

Mine, I think.

Brian

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

[Nicolas C. <war...@fr...>]

> You have two types (Enum and Stream) and a clear way to distinguish
> them (whether count always makes sense). If you merge them, you push
> the distinguishing feature to runtime.
>
> Also, it's not clear what the semantics of count on Stream are. Consider
> Stream.of_list; does it do one traversal on creation to take the count?
> Does it do it on the first call to count?  What if it's on a List with
> setcdr?  Should count be treated as an expensive or an inexpensive op?
>
> I think it makes sense to create a stream from an enum, but the opposite
> is not true.  I think we are lucky count is there to remind us.  If you
> agree with this, then the two types should not be unified.

I totally agree with you here.
The only thing that should be mentionned, is that you can always use Enum
instead of Stream, because it's better :
- if the user doesn't need count, then it's better because he still can use
all functionnal ops in Enum , as well as of_enum implementations in several
data structures
- if the user does need count, then Enum is providing the best way of doing
it (that is : actually really "counting" elements, one by one) in an
efficient way (see Enum.force) since only the first call to count will be
costly.

Nicolas Cannasse

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

[Nicolas C. <war...@fr...>]

> > 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

Errr...
I didn't think about recursive structures. It's true that having Enum.next()
would be here very better.
So ok let's add :
    val next : 'a Enum.t -> 'a option

(updated CVS)

> 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).

Since you're building a tree you don't need to be tail rec ( the stack will
grow in O(log n) ! )

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

I don't agree here :
- the new "exported" next is returning 'a option and that's a good thing (
no need to catch exception, code is more clear )
- BUT the internal next is most of the time "concatening" the next functions
in a purely functional way, so for example after two Enum.maps and doing an
Enum.iter, you'll have to check the None/Some three times ! Raising an
exception which propagate to the upper level is really a better choice.
- this choice is only making the code a little harder for the Enum modules,
other modules will never have to catch No_more_elements.

I think this is a good compromise.

Nicolas Cannasse

Re: [Ocaml-lib-devel] Enum.iter2

[Nicolas C. <war...@fr...>]

> Is there a reason why Enum.iter2 does index stuff?

Certainly a too fast copy/fast from Enum.iter2i  , not mine but it's been
properly fixed.

Thanks again for the report,
Nicolas Cannasse

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

[Manos R. <er...@cs...>]

On Mon, May 26, 2003 at 06:49:15PM -0500, Brian Hurt wrote:
> 
> Replying to myself...
> 
> On Mon, 26 May 2003, Brian Hurt wrote:
> 
> > But you're right, count needs to be an optional thing.
> > 
> 
> val count: ExtStream.t -> int option
> 
> where a return value of Some x means the stream has x elements, and a 
> return value of None means that count is not implemented.  This has the 
> advantage of roping the type checker in to make sure everyone checks for 
> the non-implemented version.

You have two types (Enum and Stream) and a clear way to distinguish 
them (whether count always makes sense). If you merge them, you push 
the distinguishing feature to runtime. 

Also, it's not clear what the semantics of count on Stream are. Consider
Stream.of_list; does it do one traversal on creation to take the count?
Does it do it on the first call to count?  What if it's on a List with
setcdr?  Should count be treated as an expensive or an inexpensive op?

I think it makes sense to create a stream from an enum, but the opposite
is not true.  I think we are lucky count is there to remind us.  If you
agree with this, then the two types should not be unified. 

-- Manos

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

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

Replying to myself...

On Mon, 26 May 2003, Brian Hurt wrote:

> But you're right, count needs to be an optional thing.
> 

val count: ExtStream.t -> int option

where a return value of Some x means the stream has x elements, and a 
return value of None means that count is not implemented.  This has the 
advantage of roping the type checker in to make sure everyone checks for 
the non-implemented version.

Now, two possibilities for doing a destructive count (i.e. one that clones 
the ExtStream and then reads ahead to see how many items are left).  The 
first one is:

val destructive_count : ExtStream.t -> int

let destructive_count enum =
    match enum.count () with
        Some x -> x
        | None ->
            let e = ExtStream.clone enum in
            let rec loop count =
                match e.next() with
                    None -> count
                    | Some _ -> loop (count + 1)
            in
            loop 0

i.e. we clone and loop everytime destructive_count is called.

The other one is:

val destructive_count: ExtStream.t -> ExtStream.t

let destructive_count enum =
    let e = ExtStream.clone enum in
    let rec loop count =
        match e.next () in
            None -> count
            | Some _ -> loop (count + 1)
    in
    let countref = ref (loop 0) in
    let next () =
        match enum.next () with
            None -> None
            | Some x -> decr countref; Some x
    and count () = !countref in
    ExtStream.make next count

In this case, we run through the enumeration only once- and create a new 
enumeration which decrements a reference every call to next.

There are advantages and disadvantages to each.

Brian

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

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

On Mon, 26 May 2003, Manos Renieris wrote:

> On Mon, May 26, 2003 at 05:51:36PM -0500, Brian Hurt wrote:
> > 
> > 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
> 
> On streams generated from list's or files, count is not a sensible
> operation, or am I mistaken? 
> 

From lists, it's an O(N) operation but easy enough (List.length).  For any 
datastructure where traversing the elements is not destructive, count is 
also easily doable.

But for files, "traversing the elements" is destructive- you read the 
file.  And if the file really is the console and the user typing stuff in, 
you can't just rewind and reread the file either.  At which point you need 
to create the interim list of objects.

But you're right, count needs to be an optional thing.

Brian

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

[Manos R. <er...@cs...>]

On Mon, May 26, 2003 at 05:51:36PM -0500, Brian Hurt wrote:
> 
> 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

On streams generated from list's or files, count is not a sensible
operation, or am I mistaken? 

-- Manos

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

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

[Nicolas C. <war...@fr...>]

> 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() ). 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.

Nicolas Cannasse

[Ocaml-lib-devel] Re: some proposals

[Alan P. <ap...@re...>]

In article <slr...@re...>, Alan Post wrote:
> 
> The perl map function allows the number of outgoing items to be
> other than 1, for instance:
> 
>   my @l2 = map { if ( filter( $_ ) { $_ } else {()}} @l1;
> 
> or:
> 
>   my %h = map { $_, f( $_ )} @l;

I just realized that perl map is simply:

  let merge_map f e = Enum.concat (Enum.map List.enum (Enum.map f e))

[Ocaml-lib-devel] Enum.iter2

[Alan P. <ap...@re...>]

Is there a reason why Enum.iter2 does index stuff?  Currently the
implementation is:

let iter2 f t u =
        let rec loop idx =
                f (t.next()) (u.next());
                loop (idx + 1)
        in
        try
                loop 0
        with
                No_more_elements -> ()


Why not:

let iter2 f t u =
        let rec loop () =
                f (t.next()) (u.next());
                loop ()
        in
        try
                loop ()
        with
                No_more_elements -> ()

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

[Brian H. <bh...@sp...>]

Added a create function in place of the old empty.  Fixed queue_to_string 
while I was in there to use a string buffer instead of just endlessly 
concating strings.  This should be more efficient.  Note that priorities 
are still implicitly part of the data.  Not that I'm opposed to making 
priorities just ints, but one major change at a time.

Also todo: to_enum, of_enum, to_stream, and of_stream should be added.  
The to_* should be both by priority and by key.

Brian

Re: [Ocaml-lib-devel] Data structures table

[John M. S. <sk...@oz...>]

Brian Hurt wrote:

> Yeah yeah, replying to myself is bad.  Anyways, I wanted to send out an 
> example of HTML for people to look at and critique.
> 
> Having played with this, I definately want to write a HTML generator for 
> this page.  In Ocaml, natch.  Otherwise maintainance will be nigh unto 
> impossible.
> 

Use interscript!

http://interscript.sourceforge.net

Here is some code:

------
@set_title('Extlib Performance')
@head(1,'Operation costs')
Here is a performance table for
various data structures
@p()
@begin_table('oper','list','array''hash')
@table_row('append','O(1)','O(N)','N/A')
@table_row('prepend','O(1)','O(N)','N/A')
@table_row('magicr','O(1)','O(N)','O(1)')
@end_table()
@p()
--------------

This input can be used to simultaneously
generate HTML (in two formats), LaTeX, Lout,
and plain text (and even nroff if someone
would care to write an nroff weaver).

BTW: the stuff after the @ sign is not
magical interscript stuff. No,
it is any Python code you want to write
(the functions such as 'begin_table' are just part of the
standard library).

This implies you can generate documentation easily
with Python script. Indeed, you can generate
code too (since its actually a literate programming
tool).

-- 
John Max Skaller, mailto:sk...@oz...
snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia.
voice:61-2-9660-0850

Re: [Ocaml-lib-devel] some proposals

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

On Fri, 23 May 2003, Nicolas Cannasse wrote:

> > Which means we're probably stuck with something like:
> >
> > let Int.compare x y = if (x < y) then -1 else if (x > y) then 1 else 0
> 
> Uh !
> This time Brian you're using up to TWO times polymorphic comparison !

You're right.  Need a typecast:

let Int.compare (x: int) (y: int) = if (x < y) then -1 else if (x > y) 
then 1 else 0



> I think the most easy solution is really to use the substraction, but that
> will cause the problems you showed with max_int / min_int , and doing some
> previous boundary tests before return x - y will increase the cost of it. So
> my conclusion is this is an user-specific problem (some might need max_int
> while some might not ) which should be addressed by not adding the module
> Int to the ExtLib, although it was a good idea.

Actually, handling the corner cases is a good argument, IMHO, *FOR* adding 
class Int.  This strikes me as being a common error.

> 
> About the partial_map, this can be done using a fold_left, which is more
> appropriate since you don't allocate None/Some blocks . But I think perhaps
> fold_left/right are not so easy to use in the first place, so maybe having a
> partial_map would be nice , but I would rename it to filter_map since this
> can be done using one map + one filter.

Allocating the option blocks doesn't worry me much.  I assumed that we 
wanted to a) avoid allocating an unnecessary interim list, and b) wanted 
to construct the list forwards, as opposed to doing a List.rev.  If either 
of these are relaxed, then yes, the function can be fairly easily 
implemented given existing functions.

> 
> BTW, I would prefer a more simple version of the Brian one, which does not
> need two loops :
> 
> let filter_map f l =
>     let rec loop dst = function
>         | [] -> ()
>         | h :: t ->
>             match f t with
>             | None -> loop dst t
>             | Some x ->
>                     let r = [ x ] in
>                     Obj.set_field (Obj.repr dst) 1 (Obj.repr r);
>                     loop r t
>     in
>     let dummy = [ Obj.magic () ] in
>     loop dummy l;
>     List.tl dummy
> 

I forgot about this trick.  This is a better implementation.

Brian

Re: [Ocaml-lib-devel] Re: ExtList / Enum updates

[Nicolas C. <war...@fr...>]

> > Enum - added :
> >     val filter_map : ('a -> 'b option) -> 'a t -> 'b t
> >     val clone : 'a t -> 'a t
> 
> Is there a reason why Enum.filter is not implemented using Enum.from?
> 
> As in:
> 
> let filter f t =
>     let rec next () =
>         let x = t.next() in
>         if f x then x else next()
>     in
>     from next

Historical reasons. filter was defined before from.
I will update the sources, thanks for the report.

Nicolas Cannasse

[Ocaml-lib-devel] Re: ExtList / Enum updates

[Alan P. <ap...@re...>]

In article <014501c320d5$657a69b0$2713f9ca@WARP>, Nicolas Cannasse wrote:
> 
> Enum - added :
>     val filter_map : ('a -> 'b option) -> 'a t -> 'b t
>     val clone : 'a t -> 'a t

Is there a reason why Enum.filter is not implemented using Enum.from?

As in:

let filter f t =
    let rec next () =
        let x = t.next() in
        if f x then x else next()
    in
    from next

Re: [Ocaml-lib-devel] some proposals

[<Ala...@en...>]

On Thu, 22 May 2003, Brian Hurt wrote:

> On Thu, 22 May 2003, Brian Hurt wrote:
>
> > Optimization question for the list at large: would doing:
> >
> > let Int.compare (x : int) (y : int) : int = Pervasives.compare x y
> >
> > be enough to allow the optimizer to do it's thing?
> >
>
> Answering my own question: looks like no.

No for the current OCaml release, yes for the next one... Xavier
implemented strength reduction for Pervasives.compare (which means it will
be specialized for all integers types, floats, strings).

See:
http://camlcvs.inria.fr/cgi-bin/cvsweb.cgi/ocaml/bytecomp/translcore.ml.diff?r1=1.87&r2=1.88&f=h
http://camlcvs.inria.fr/cgi-bin/cvsweb.cgi/ocaml/byterun/ints.c.diff?r1=1.38&r2=1.39&f=h


        Objective Caml version 3.06+34 (2003-05-21)

# let f (x:int) y = compare x y;;
        closure L1, 0
        push
        acc 0
        push
        const "f"
        push
        getglobal Toploop!
        getfield 1
        appterm 2, 4
        restart
L1:     grab 1
        acc 1
        push
        acc 1
        ccall int_compare, 2
        return 2




-- Alain

[Ocaml-lib-devel] ExtList / Enum updates

[Nicolas C. <war...@fr...>]

ExtList - added :
    val filter_map : ('a -> 'b option) -> 'a list -> 'b list
    val unique : ?cmp:('a -> 'a -> bool) -> 'a list -> 'a list

Enum - added :
    val filter_map : ('a -> 'b option) -> 'a t -> 'b t
    val clone : 'a t -> 'a t

Enum.clone will enable you to enumerate several times over the same enum ,
the implementation is quite efficient.

Nicolas Cannasse

Re: [Ocaml-lib-devel] some proposals

[Remi V. <van...@la...>]

"Nicolas Cannasse" <war...@fr...> writes:

>> Which means we're probably stuck with something like:
>>
>> let Int.compare x y = if (x < y) then -1 else if (x > y) then 1 else 0
>
> Uh !
> This time Brian you're using up to TWO times polymorphic comparison
> !

well, If it is rewrite as :

let compare (x : int) (y:int) = if (x < y) then -1 else if (x > y) then 1 else 0

then there is no use of the polymorphic comparison function

[...]


-- 
Rémi Vanicat
va...@la...
http://dept-info.labri.u-bordeaux.fr/~vanicat

Re: [Ocaml-lib-devel] Re: some proposals

[Nicolas C. <war...@fr...>]

 > I considered implementing this as an enum.  But here's the problem: count
> requires you to know in advance how many elements you have.  The only way
> I can see doing this would be to create a list of pre-converted elements
> that didn't return None.  A stream might be a better choice.

Please remember I just added Enum.from !

--- Enum module -----

let filter_map f e =
    let rec next () =
        match f e.next with
        | None -> next()
        | Some x -> x
    in
    from next

-------------------

Nicolas Cannasse

Re: [Ocaml-lib-devel] some proposals

[Nicolas C. <war...@fr...>]

> Which means we're probably stuck with something like:
>
> let Int.compare x y = if (x < y) then -1 else if (x > y) then 1 else 0

Uh !
This time Brian you're using up to TWO times polymorphic comparison !
I think the most easy solution is really to use the substraction, but that
will cause the problems you showed with max_int / min_int , and doing some
previous boundary tests before return x - y will increase the cost of it. So
my conclusion is this is an user-specific problem (some might need max_int
while some might not ) which should be addressed by not adding the module
Int to the ExtLib, although it was a good idea.

About the partial_map, this can be done using a fold_left, which is more
appropriate since you don't allocate None/Some blocks . But I think perhaps
fold_left/right are not so easy to use in the first place, so maybe having a
partial_map would be nice , but I would rename it to filter_map since this
can be done using one map + one filter.

BTW, I would prefer a more simple version of the Brian one, which does not
need two loops :

let filter_map f l =
    let rec loop dst = function
        | [] -> ()
        | h :: t ->
            match f t with
            | None -> loop dst t
            | Some x ->
                    let r = [ x ] in
                    Obj.set_field (Obj.repr dst) 1 (Obj.repr r);
                    loop r t
    in
    let dummy = [ Obj.magic () ] in
    loop dummy l;
    List.tl dummy

Nicolas Cannasse

Re: [Ocaml-lib-devel] Re: some proposals

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

On Thu, 22 May 2003, Alan Post wrote:

> The perl map function allows the number of outgoing items to be
> other than 1, for instance:
> 
>   my @l2 = map { if ( filter( $_ ) { $_ } else {()}} @l1;
> 
> or:
> 
>   my %h = map { $_, f( $_ )} @l;
> 
> I imagine it would be a bit tricky to implement an Enum function like
> that ("merge_map"?), but it would generalize the partial map function
> above.
> 
> 
> A more general question:  how many map/iterate functions will be a
> part of the data structures, as opposed to having users stick to the
> Enum versions?  For instance,
> 
>   List.map f l 
> 
>     vs
> 
>   List.of_enum (Enum.map f (List.enum l))
> 
> Will each datastructure have its own map function, to make things
> convenient for users?
> 

I considered implementing this as an enum.  But here's the problem: count 
requires you to know in advance how many elements you have.  The only way 
I can see doing this would be to create a list of pre-converted elements 
that didn't return None.  A stream might be a better choice.  

let stream_partial_map f src =
    let rec next curr_ref x =
        match !curr_ref with
          [] -> None
          | h :: t -> 
              curr_ref := t;
              match f h with
                  None -> next curr_ref x
                  | Some t -> Some t
    in
    Stream.from (next (ref src))
;;


But I hate having two different almost-identical-but-subtly-different
ways of doing things.  I think that instead of Enum module, we should 
consider an ExtStream module, with Enum functionality.

Brian

[Ocaml-lib-devel] Re: some proposals

[Alan P. <ap...@re...>]

In article <200...@ro...eak>, Michal Moskal wrote:
> 
> 1) For extList:
> 
> val partial_map : ('a -> 'b option) -> 'a list -> 'b list
> 
> let rec partial_map f = function
>  | x :: xs ->
>     begin
>       match f x with
>       | Some y -> y :: list_partial_map f xs
>       | None -> list_partial_map f xs
>     end
>  | [] -> []

The perl map function allows the number of outgoing items to be
other than 1, for instance:

  my @l2 = map { if ( filter( $_ ) { $_ } else {()}} @l1;

or:

  my %h = map { $_, f( $_ )} @l;

I imagine it would be a bit tricky to implement an Enum function like
that ("merge_map"?), but it would generalize the partial map function
above.


A more general question:  how many map/iterate functions will be a
part of the data structures, as opposed to having users stick to the
Enum versions?  For instance,

  List.map f l 

    vs

  List.of_enum (Enum.map f (List.enum l))

Will each datastructure have its own map function, to make things
convenient for users?