From: Michal M. <mal...@pl...> - 2003-05-22 18:43:16
|
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. 2) Int module like: module Int = struct type t = int let compare x y = x - y end To be used as input for Map.Make/Set.Make. -- : Michal Moskal :: http://www.kernel.pl/~malekith : GCS {C,UL}++++$ a? !tv : PLD Linux ::::::::: Wroclaw University, CS Dept : {E-,w}-- {b++,e}>+++ h |
From: Brian H. <bri...@ql...> - 2003-05-22 19:03:29
|
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 |
From: Brian H. <bri...@ql...> - 2003-05-22 19:06:08
|
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 |
From: Nicolas C. <war...@fr...> - 2003-05-23 01:58:21
|
> 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 |
From: Remi V. <van...@la...> - 2003-05-23 02:37:59
|
"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 |
From: Brian H. <bri...@ql...> - 2003-05-23 15:13:04
|
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 |
From: <Ala...@en...> - 2003-05-23 06:16:27
|
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 |
From: Alan P. <ap...@re...> - 2003-05-22 22:33:06
|
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? |
From: Brian H. <bri...@ql...> - 2003-05-22 22:52:34
|
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 |
From: Nicolas C. <war...@fr...> - 2003-05-23 02:04:35
|
> 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 |
From: Alan P. <ap...@re...> - 2003-05-25 07:37:28
|
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)) |