OCaml ExtLib

On Thu, 22 May 2003, 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
>   | [] -> []
> 
> modulo tail-recursion tricks.

First cut:


let partial_map f src =
    let rec loop dst lst =
        match lst with
            [] -> ()
            | h :: t ->
                match f h with
                    None -> loop dst t
                    | Some b -> 
                        let r = [ b ] in
                        Obj.set_field (Obj.repr dst) 1 (Obj.repr r);
                        loop r t
    in
    let rec find_head lst =
         match lst with
             [] -> []
             | h :: t ->
                 match f h with
                     None -> find_head t
                     | Some b ->
                         let r = [ b ] in
                         loop r t;
                         r
    in
    find_head src


> 
> 2) Int module like:
> 
> module Int =
>   struct
>       type t = int
>       let compare x y = x - y
>   end

Compare needs to be a little bit more intelligent to handle carry.  
Consider that compare min_int max_int = 1, i.e. min_int > max_int.  While 
Pervasive.compare min_int max_int = -1 (which is correct).

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?

Brian

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.

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

Brian

In article <20030522184129.GA16718@...>, 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?

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

> 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

> 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

"Nicolas Cannasse" <warplayer@...> 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
vanicat@...
http://dept-info.labri.u-bordeaux.fr/~vanicat

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

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

In article <slrnbcqjh0.6fv.apost@...>, 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))