From: Eric C. C. <ec...@cm...> - 2003-02-26 16:39:02
|
Here are the functions (primarily extensions to List and String) that I find myself re-using. The set-theoretic and combinatoric ones are probably too simplistic for general use, but I'll throw them out there for discussion. -- Eric C. Cooper e c c @ c m u . e d u ---- (* * Additions to the List module. *) (* Generate the range of integers [a; a+1; ...; b] *) val range : int * int -> int list (* List equivalent of Array.init *) val listi : int -> (int -> 'a) -> 'a list (* List equivalent of Array.mapi *) val mapi : (int -> 'a -> 'b) -> 'a list -> 'b list (* List equivalent of Array.iteri *) val iteri : (int -> 'a -> unit) -> 'a list -> unit (* Reverse assoc *) (* can also add rassq, mem_rassoc/rassq, remove_rassoc/rassq if needed *) val rassoc : 'b -> ('a * 'b) list -> 'a (* Tail-recursively compute rev (map f list1) @ list2 *) val rev_map_append : ('a -> 'b) -> 'a list -> 'b list -> 'b list (* Split [x1; x2; ...; xN] into [x1; ...; x{n}] and [x{n+1}; ...; xN] *) val split_nth : int -> 'a list -> 'a list * 'a list (* Tail-recursively split [x1; x2; ...; xN] into [x{n}; ...; x1] and [x{n+1}; ...; xN] *) val rev_split_nth : int -> 'a list -> 'a list * 'a list (* Return the last element of a list. *) val last : 'a list -> 'a (* Insert x at position n in list. Position 0 places x at the front; position (length list) places x at the end. *) val insert : 'a -> int -> 'a list -> 'a list (* Remove first occurrence of x, if any, from list. *) val remove_first : 'a -> 'a list -> 'a list (* Remove all occurrences of x from list. *) val remove : 'a -> 'a list -> 'a list (* Remove a subset of elements from a list. *) val remove_subset : 'a list -> 'a list -> 'a list (* Rotate each element of a list to the left, so that the head becomes the last element. *) val rotate_left : 'a list -> 'a list (* Homogeneous version of List.fold_left. Uses the head of the list as the initial value. *) val fold : ('a -> 'a -> 'a) -> 'a list -> 'a (* Test whether the first list is a subset of the second. *) val subset : 'a list -> 'a list -> bool (* Return cartesian product of two lists. *) val product : 'a list -> 'b list -> ('a * 'b) list (* Return all sublists of a list. *) val subsets : 'a list -> 'a list list (* Return all n-element sublists of a list. *) val choose : int -> 'a list -> 'a list list (* Return all sublists with up to n elements. *) val choose_up_to : int -> 'a list -> 'a list list (* Remove duplicates from a sorted list, using a sort-style comparison function that returns 0 for equality. *) val uniq : ('a -> 'a -> int) -> 'a list -> 'a list (* * Additions to the String module. *) (* String equivalents of Array.fold_left and Array.fold_right *) val string_fold_left : ('a -> char -> 'a) -> 'a -> string -> 'a val string_fold_right : (char -> 'a -> 'a) -> 'a -> string -> 'a (* Convert between strings and lists of chars. *) val explode : string -> char list val implode : char list -> string (* Convert between strings and lists of ints in the range 0 .. 255 *) val explode_bytes : string -> int list val implode_bytes : int list -> string (* Like [index_from] but searches at most [len] chars. *) (* can also add bounded_rindex if needed *) val bounded_index : string -> pos:int -> len:int -> char -> int (* * Miscellaneous control structures. *) (* Compute f (g x) *) (* It would be nice to have a standard infix operator for this. *) val compose : ('b -> 'c) -> ('a -> 'b) -> 'a -> 'c (* Compute f^n x *) val iterate : ('a -> 'a) -> int -> 'a -> 'a (* Invoke (f ()) n times, for side effects. *) val repeat : int -> (unit -> unit) -> unit (* Apply f to 0 .. n-1, for side effects. *) val dotimes : int -> (int -> unit) -> unit |
From: Luc M. <Luc...@cv...> - 2003-02-26 17:01:08
|
Perhaps it's a dummy question but why List.create doesn't exist ? module AdvancedList = struct let create n v = let rec create_aux l n v = match n with | 0 -> l | _ -> (create_aux (v::l) (n-1) v) in create_aux [] n v;; let rec create_with_fun f n = match n with | 0 -> [] | _ -> f() :: (create_with_fun f (n - 1));; end -- Luc...@cv... |
From: Michal M. <mal...@pl...> - 2003-02-26 17:16:41
|
On Wed, Feb 26, 2003 at 11:38:47AM -0500, Eric C. Cooper wrote: > (* Invoke (f ()) n times, for side effects. *) > > val repeat : int -> (unit -> unit) -> unit > > (* Apply f to 0 .. n-1, for side effects. *) > > val dotimes : int -> (int -> unit) -> unit I belive for loop is more readable: repeat 20 f == for i = 1 to 20 do f () done dotimes 20 f == for i = 0 to 19 do f i done and gives more possiblities. Don't have strong opinions about other stuff here. -- : Michal Moskal ::::: malekith/at/pld-linux.org : GCS {C,UL}++++$ a? !tv : PLD Linux ::::::: Wroclaw University, CS Dept : {E-,w}-- {b++,e}>+++ h |
From: fva <fv...@ts...> - 2003-02-27 09:51:50
|
Eric C. Cooper wrote: >Here are the functions (primarily extensions to List and String) that >I find myself re-using. The set-theoretic and combinatoric ones are >probably too simplistic for general use, but I'll throw them out there >for discussion. > > How would you go about packaging these in the extlib so that they can be more or less seamlessly integrated with the stdlib. A single overarching file-module? Regards, Fran Valverde |
From: Eric C. C. <ec...@cm...> - 2003-02-27 19:11:51
|
On Thu, Feb 27, 2003 at 10:58:20AM +0100, fva wrote: > How would you go about packaging these in the extlib so that they can be > more or less seamlessly integrated with the stdlib. A single overarching > file-module? As someone suggested earlier on this list, I'd favor something like: module Ext = struct module List = struct include List ... <our extensions go here> end module String = struct include String ... <our extensions go here> end ... end -- Eric C. Cooper e c c @ c m u . e d u |
From: Nicolas C. <war...@fr...> - 2003-02-28 02:31:38
|
> > How would you go about packaging these in the extlib so that they can be > > more or less seamlessly integrated with the stdlib. A single overarching > > file-module? > > As someone suggested earlier on this list, I'd favor something like: > > module Ext = > struct > module List = > struct > include List > ... <our extensions go here> > end > > module String = > struct > include String > ... <our extensions go here> > end > ... > end Linkage of binaries in bytecode application is made on a per-file basis ( and not per-module or per-function ). So in order to keep the bytecode size small, we'll have to use several files (that's just what's the stdlib is doing). Nicolas Cannasse |
From: Nicolas C. <war...@fr...> - 2003-02-27 10:52:29
|
> (* > * Additions to the List module. > *) > > (* Generate the range of integers [a; a+1; ...; b] *) > > val range : int * int -> int list would prefer : range : int -> int -> int list since it's not causing any overhead due to the tuple allocation ( integer are unboxed ) > (* List equivalent of Array.init *) > > val listi : int -> (int -> 'a) -> 'a list ok , let's call it ExtList.init ! and so you have let range a b = ExtList.init (b - a) (fun x -> x+a) and if I agree that List.init is missing, I don't think that the "range" is worth including in ExtList > (* List equivalent of Array.mapi *) > > val mapi : (int -> 'a -> 'b) -> 'a list -> 'b list > val iteri : (int -> 'a -> unit) -> 'a list -> unit ok I buy it > (* Reverse assoc *) > (* can also add rassq, mem_rassoc/rassq, remove_rassoc/rassq if needed *) > > val rassoc : 'b -> ('a * 'b) list -> 'a I reallly don't like theses. The usage of them are far from obvious > (* Tail-recursively compute rev (map f list1) @ list2 *) > > val rev_map_append : ('a -> 'b) -> 'a list -> 'b list -> 'b list same : I don't see the point This function seems very particular, I haven't ever needed it (or perhaps I don't remember) And I would like something doing that, I think I wouln't even check in any StandardLibrary if it exists. > (* Split [x1; x2; ...; xN] into [x1; ...; x{n}] and [x{n+1}; ...; xN] *) > > val split_nth : int -> 'a list -> 'a list * 'a list Agree, Looks a little like the npop from MList > (* Tail-recursively split [x1; x2; ...; xN] into > [x{n}; ...; x1] and [x{n+1}; ...; xN] *) > > val rev_split_nth : int -> 'a list -> 'a list * 'a list Don't agree. If users wants tail-recusive calls for such functions, I think they have to implement it since we're not going to provide for all the non tail recursive functions a corresponding tail recursive one. > (* Return the last element of a list. *) > > val last : 'a list -> 'a Agree - need an exception :) > (* Insert x at position n in list. > Position 0 places x at the front; > position (length list) places x at the end. *) > > val insert : 'a -> int -> 'a list -> 'a list Agree > (* Remove first occurrence of x, if any, from list. *) > val remove_first : 'a -> 'a list -> 'a list > > (* Remove all occurrences of x from list. *) > val remove : 'a -> 'a list -> 'a list > > (* Remove a subset of elements from a list. *) > val remove_subset : 'a list -> 'a list -> 'a list Actually I wonder if when you're using theses, you're not actualy using somehow a mutable list... > (* Rotate each element of a list to the left, > so that the head becomes the last element. *) > > val rotate_left : 'a list -> 'a list Too much particular > (* Homogeneous version of List.fold_left. > Uses the head of the list as the initial value. *) > > val fold : ('a -> 'a -> 'a) -> 'a list -> 'a Same > (* Test whether the first list is a subset of the second. *) > > val subset : 'a list -> 'a list -> bool Agree, but I would add a functional comparator as first parameter. Perhaps when using such comparators, we could use an optional argument ?comp having a default of ( = ) > (* Return cartesian product of two lists. *) > > val product : 'a list -> 'b list -> ('a * 'b) list "join" is a better name. > (* Return all sublists of a list. *) > > val subsets : 'a list -> 'a list list Pfiouu You're doing strange things with Ocaml , aren't you ? :) Statistics, is it ? > (* Return all n-element sublists of a list. *) > > val choose : int -> 'a list -> 'a list list > > (* Return all sublists with up to n elements. *) > > val choose_up_to : int -> 'a list -> 'a list list Too particular > (* Remove duplicates from a sorted list, > using a sort-style comparison function that returns 0 for equality. *) > > val uniq : ('a -> 'a -> int) -> 'a list -> 'a list Why do not use a ('a -> 'a -> bool) on unsorted list ? complexity is the same > (* > * Additions to the String module. > *) > > (* String equivalents of Array.fold_left and Array.fold_right *) > > val string_fold_left : ('a -> char -> 'a) -> 'a -> string -> 'a > val string_fold_right : (char -> 'a -> 'a) -> 'a -> string -> 'a > > (* Convert between strings and lists of chars. *) > > val explode : string -> char list > val implode : char list -> string Theses four are interesting, but I don't realy see the need of using Strings as char list. Could you tell me about it ? > (* Convert between strings and lists of ints in the range 0 .. 255 *) > > val explode_bytes : string -> int list > val implode_bytes : int list -> string > > (* Like [index_from] but searches at most [len] chars. *) > (* can also add bounded_rindex if needed *) > > val bounded_index : string -> pos:int -> len:int -> char -> int Same > (* > * Miscellaneous control structures. > *) > > (* Compute f (g x) *) > (* It would be nice to have a standard infix operator for this. *) > > val compose : ('b -> 'c) -> ('a -> 'b) -> 'a -> 'c Agree > (* Compute f^n x *) > > val iterate : ('a -> 'a) -> int -> 'a -> 'a Agree > (* Invoke (f ()) n times, for side effects. *) > > val repeat : int -> (unit -> unit) -> unit > > (* Apply f to 0 .. n-1, for side effects. *) > > val dotimes : int -> (int -> unit) -> unit Better with a "for" loop. Done. Nicolas Cannasse |
From: Fernando A. <fer...@cc...> - 2003-02-27 17:52:25
|
On Thu, Feb 27, 2003 at 07:51:43PM +0900, Nicolas Cannasse wrote: > ok , let's call it ExtList.init ! I'd prefer ExtLib.List.int That way, I can switch from StdLib.List to ExtLib.List by just "opening" ExtLib in my sources. By the way, what if we propose to the caml team that the modules in the standard library be all under a StdLib module? Fernando |
From: Nicolas C. <war...@fr...> - 2003-02-28 02:41:42
|
> > ok , let's call it ExtList.init ! > > I'd prefer ExtLib.List.int > > That way, I can switch from StdLib.List to ExtLib.List by just > "opening" ExtLib in my sources. This way, you're supposing that ExtLib.List will be a reimplementation of the List module... I don't that's the purpose here. Let's just say that ExtList contains additionnals functions using the List.t type ( aka 'a list ) and that you can use them just with "open ExtList". Don't you think ? > By the way, what if we propose to the caml team that the modules in the > standard library be all under a StdLib module? Same remarks. ExtLib is not a different implementation, so switching between StdLib and ExtLib does not make sense. Nicolas Cannasse |
From: Fernando A. <fer...@cc...> - 2003-02-28 04:10:54
|
On Fri, Feb 28, 2003 at 11:40:55AM +0900, Nicolas Cannasse wrote: > > I'd prefer ExtLib.List.int > > > > That way, I can switch from StdLib.List to ExtLib.List by just > > "opening" ExtLib in my sources. > > This way, you're supposing that ExtLib.List will be a reimplementation of > the List module... I don't that's the purpose here. Let's just say that More than a reimplementation, I see it as a superset. ExtLib would pass through without change most StdLib functions, add a few missing functions and shadow the bad guys in StdLib (incorrect functions in List and so) It may also add a few sub-modules missing in StdLib, and maybe a few functions missing in Pervasives. So, "open ExtLib" will give you an enhanced OCaml environment. Fernando |
From: Nicolas C. <war...@fr...> - 2003-02-28 06:07:01
|
> > > I'd prefer ExtLib.List.int > > > > > > That way, I can switch from StdLib.List to ExtLib.List by just > > > "opening" ExtLib in my sources. > > > > This way, you're supposing that ExtLib.List will be a reimplementation of > > the List module... I don't that's the purpose here. Let's just say that > > More than a reimplementation, I see it as a superset. > > ExtLib would pass through without change most StdLib functions, add a few > missing functions and shadow the bad guys in StdLib (incorrect functions > in List and so) > > It may also add a few sub-modules missing in StdLib, and maybe a few > functions missing in Pervasives. So, "open ExtLib" will give you an > enhanced OCaml environment. I would actually like to have that, but : - I don't really agree when you're qualifying "bad guys" some stdlib functions. and I don't think that the caml team will agree also :) - the only "bad guys" for me are the functions which are raising either Invalid_argument or Failure when users are supposed catch it to handle (for example, creating an Array with a negative size is a good "invalid_argument" raise case, while List.hd is not ) - we can't modify theses functions without giving them a different name ( for obvious stdlib compatibily reasons ) but when can provide different implementations ( such as stoi & stof in the ExtLib.String proposed in v0.1 as alternatives to int_of_string & float_of_string ) The last point is about compilation and module linkage. If you want to do "open ExtLib" and then "open List" for exemple, then ExtLib have to be ONE big module (perhaps several files linked together with the -pack option, but still one big cmo ) and so will always be entirely linked with your bytecode if you're using only one function of it... so that'll prevent us from adding new modules since each time it will get bigger and bigger. If you have another structure/compilation proposal.... Regards, Nicolas Cannasse |
From: fva <fv...@ts...> - 2003-02-28 10:02:41
|
Nicolas Cannasse wrote: >The last point is about compilation and module linkage. >If you want to do "open ExtLib" and then "open List" for exemple, then >ExtLib have to be ONE big module (perhaps several files linked together with >the -pack option, but still one big cmo ) and so will always be entirely >linked with your bytecode if you're using only one function of it... so >that'll prevent us from adding new modules since each time it will get >bigger and bigger. If you have another structure/compilation proposal.... > I recall the question about namespaces in the COAN thread and X. Leroy saying that the -pack option was still unstable... Could we ask for it to "drift" so that the support would be merely "namespatial" in the sense that no big cmo file got build out of the multiple cmo's being packed... Or at least that cmos generated with -pack were rather stubs for the modules being assembled so that they didn't have to be loaded as a *whole*. I'm not into compiler/linker construction so I don't know about the complexity of this but it doesn't look altogether unreasonable to me... It's for the benefit of the generated code to be lean! Regards, Fran Valverde |
From: Nicolas C. <war...@fr...> - 2003-02-28 10:27:05
|
> >The last point is about compilation and module linkage. > >If you want to do "open ExtLib" and then "open List" for exemple, then > >ExtLib have to be ONE big module (perhaps several files linked together with > >the -pack option, but still one big cmo ) and so will always be entirely > >linked with your bytecode if you're using only one function of it... so > >that'll prevent us from adding new modules since each time it will get > >bigger and bigger. If you have another structure/compilation proposal.... > > > > I recall the question about namespaces in the COAN thread and X. Leroy > saying that the -pack option was still unstable... Could we ask for it > to "drift" so that the support would be merely "namespatial" in the > sense that no big cmo file got build out of the multiple cmo's being > packed... Or at least that cmos generated with -pack were rather stubs > for the modules being assembled so that they didn't have to be loaded as > a *whole*. I'm not into compiler/linker construction so I don't know > about the complexity of this but it doesn't look altogether unreasonable > to me... It's for the benefit of the generated code to be lean! I don't think this kind of hack will be done by the caml team like this. It takes time to find a good way to do it, and might not be done for the 3.07 release. So we cannot rely on it, and have to find our own packaging way. Nicolas Cannasse |
From: Eric C. C. <ec...@cm...> - 2003-02-27 19:29:11
|
On Thu, Feb 27, 2003 at 07:51:43PM +0900, Nicolas Cannasse wrote: > > (* Generate the range of integers [a; a+1; ...; b] *) > > > > val range : int * int -> int list > > would prefer : > range : int -> int -> int list > since it's not causing any overhead due to the tuple allocation ( integer > are unboxed ) That's a reasonable argument. I like the suggestion of mathematical "interval notation" with range (1, 10), but don't feel strongly about it. > > (* Reverse assoc *) > > (* can also add rassq, mem_rassoc/rassq, remove_rassoc/rassq if needed *) > > > > val rassoc : 'b -> ('a * 'b) list -> 'a > > I reallly don't like theses. The usage of them are far from obvious My old Lisp habits are showing, I guess. > > (* String equivalents of Array.fold_left and Array.fold_right *) > > > > val string_fold_left : ('a -> char -> 'a) -> 'a -> string -> 'a > > val string_fold_right : (char -> 'a -> 'a) -> 'a -> string -> 'a I really think these are useful. For example: let checksum data = string_fold_left (fun n c -> (n + Char.code c) mod 256) 0 data let explode string = string_fold_right (fun c list -> c :: list) [] string > > (* Convert between strings and lists of chars. *) > > > > val explode : string -> char list > > val implode : char list -> string > > Theses four are interesting, but I don't realy see the need of using Strings > as char list. Could you tell me about it ? This is another Lisp influence. I find it easier to write "functional" string manipulation with these operators (versus the Buffer module, which is more efficient for large strings, but also more imperative and less flexible -- you can't go back and insert data at the beginning or middle). Thanks for all the comments. -- Eric C. Cooper e c c @ c m u . e d u |