From: Janne H. <jjh...@gm...> - 2005-08-11 04:26:19
|
On 8/11/05, Nicolas Cannasse <war...@fr...> wrote: > > val fold_left_while : > > ('a -> 'b -> bool) -> ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a =3D <f= un> >=20 > I think too that having an exception is better than providing two functio= ns. > In general you want to stop recursion on a case that can't be treated by > your "fold" , so you're already matching into your fold, with maybe an > assert false in the case you already filtered it. It's better then to gro= up > both test+fold into a single function since I can't see good cases when y= ou > want to freely compose different folds and different stoppers. This is a good point. For some reason or the other, I tend to avoid using exceptions in this manner though, but I guess that's just all the years programming in C and C++ talking. I noticed that I can cover all my reasonable use cases easily by using List.fold_left and filtering its input with List.takewhile. This does not apply for cases which actually use the accumulation parameter for the "stop predicate" though. =20 Anyway, I'm beginning to think it might not make such a good addition after all -- at least not in its current form. > >> let split : ('a -> bool) -> 'a list -> 'a list list =3D <fun> >=20 > That one might be useful in some cases. > But it needs a new name ;) After thinking this through, I came up with an additional function called split_when. This works similarly to Exlib's split_nth except that we're not splitting based on list position but based on a predicate function. The split_when function is called break in Haskell's standard library. Here's the implementation: val split_when : ('a -> bool) -> 'a list -> 'a list * 'a list =3D <fun> (** [split_when p l] returns two lists [l1] and [l2], [l1] containing the first elements for which [p x] holds false, and [l2] the others. *) let split_when pred lst =3D let rec loop acc =3D function [] -> (acc,[]) | (x::xs) as rest -> if pred x then (acc, rest) else loop (x::acc) xs in let (start,rest) =3D loop [] lst in (rev start,rest) It is easy to write my original "split" (now called separate) function with the help of split_when: val separate : ('a -> bool) -> 'a list -> 'a list list =3D <fun> (** [separate p l] splits list [l] into sublists that do not contain elements satisfying [p x] predicate. Example:=20 [separate (fun c -> c =3D '\n') ['a'; 'b'; '\n'; 'c']] yields=20 [[['a'; 'b']; ['c']]] *) let separate pred lst =3D=20 let rec loop acc lst =3D=20 let (start,rest) =3D split_when pred lst in let acc' =3D=20 if start =3D [] then acc else start::acc in match rest with [] -> acc' | x::xs -> loop acc' xs in rev (loop [] lst) I think both split_when and separate would make good additions to ExtList. If anyone has a better name to suggest for separate, I'm all ears. Here's some test cases for separate: # separate (fun c -> c =3D '\n') ['a'; 'b'; '\n'; 'c'];; - : char list list =3D [['a'; 'b']; ['c']] # separate ((=3D) 0) [];; - : int list list =3D [] # separate ((=3D) 0) [0];; - : int list list =3D [] # separate ((=3D) 0) [1; 2; 3; 0; 4; 5; 6; 7; 0];; - : int list list =3D [[1; 2; 3]; [4; 5; 6; 7]] # separate ((=3D) 0) [0; 4; 5; 6; 7; 0];; - : int list list =3D [[4; 5; 6; 7]] # separate ((=3D) 0) [0; 4; 5; 6; 7; 0; 33];; - : int list list =3D [[4; 5; 6; 7]; [33]] # separate ((=3D) 0) [0; 0; 0];; - : int list list =3D [] Best regards, Janne |