ocaml-lib-devel — Developer's mailing list

Re: [Ocaml-lib-devel] Extlib.list.unique

[Amit D. <ami...@gm...>]

In principle, I like the idea. I don't know if I like the implementation,
though. It seems a bit too complex, and the variable names are difficult to
decipher (e.g. "ac" means "accu/accumulator", but it isn't clear what tcn
means; if you want to use short names, might as well use "x", "y", etc.)
Maybe this is going too far, but could you overload the O(n^2)
implementation with the faster one, for cases where you don't have an
ordering over elements? i.e. something like this:

let unique ?(last=3Dfalse) ?(cmp=3DNone) l =3D
match cmp with
| None -> (* old unique *)
| Some c ->
let cmp_node x y =3D c (fst x) (fst y) in
let cmp_idx x y =3D Pervasives.compare (snd x) (snd y) in

(* Sorted order, with an index for the original ordering *)
let l' =3D stable_sort cmp_node (mapi (fun i x -> (x,i)) l) in

let rec remove_dup accu =3D function
| [] -> accu
| x::xs ->
match accu with
| [] ->
remove_dup [x] xs
| (y::ys) as yl ->
if (cmp_node x y) =3D 0 then
if last then
remove_dup (x::ys) xs
else
remove_dup yl xs
else
remove_dup (x::yl) xs
in
(* Remove duplicates, restore original order,
and remove the original index. *)
map fst (stable_sort cmp_idx (remove_dup [] l'))


-Amit

On 10/21/05, sejourne_kevin <sej...@ya...> wrote:
>
> Hello evrybody.
>
> Thanks for that lib I use evryday.
>
> But, I notice that ExtList.unique is in O(n^2) this is a problem for me,
> I often use list over 100000 elements(and some time over million).
> So I wrote a replacement function that is faster O(n+n*log(n)).
> It use about 5X the space of the parameter list. On my computer (512 Mo)
> the limit before the stak overflow is just over a million.
>
>
> let delete_double_unsort ?(last=3Dfalse) ?(cmp=3DPervasives.compare) l =
=3D
> let lg =3D List.length l in
> let tcn =3D Array.make lg (List.hd l,0) in
> let rec add_num n =3D function
> [] -> ()
> | h :: t -> tcn.(n) <- (h,n) ; (add_num (succ n) t)
> in
> let () =3D add_num 0 l in
> let compare x y =3D cmp (fst x) (fst y) in
> let tcn' =3D Array.copy tcn in
> let () =3D Array.stable_sort compare tcn in
> let plg =3D lg -1 in
> let rec get_dbl ac n =3D
> if n =3D=3D plg then ac
> else
> let n' =3D n+1 in
> let h1 =3D tcn.(n) in
> let h2 =3D tcn.(n') in
> if (cmp (fst h1) (fst h2)) =3D=3D 0
> then get_dbl ((snd (if last then h1 else h2))::ac) n'
> else get_dbl ac n'
> in
> let dbl =3D get_dbl [] 0 in
> let sdbl =3D List.sort Pervasives.compare dbl in
> let rec delete n =3D function
> [] ->
> let ac =3D ref [] in
> for i =3D n to lg -1 do
> ac :=3D (fst tcn'.(i)) :: !ac
> done;
> List.rev !ac
> | na::ta when na =3D=3D (snd tcn'.(n)) -> delete (n+1) ta
> | l -> (fst tcn'.(n)) :: (delete (n+1) l)
> in delete 0 sdbl
> ;;
>
> As you can see this function support a additionnal option that let you
> select if you want delete the first or the last occurence of a term.
> For the "equivalence" with ExtList.unique set "~last:true".
>
>
> for 100000 elements :
> Extlib.list.unique : 165.850 seconds
> this function : 0.380 seconds
> for 1000000 elements :
> Extlib.list.unique : stop by error after 2 hours...
> this function : 9.600 seconds
>
>
>
> Even if you don't want to include it in the ExtLib I would be glade if
> someone know how to improve it.
>
>
>
> Here few test code:
> (*
> let bench n p =3D
> Random.self_init ();
> let rec new_list n =3D
> if n =3D=3D 0 then [] else (Random.int <http://Random.int> 100000)::(new_=
list
> (pred n))
> in
> let a_bench n =3D
> let l =3D new_list n in Gc.compact();
> (*let t1 =3D Sys.time() in ignore (delete_double_unsort_list l);*)
> (*let t1 =3D Sys.time() in ignore (delete_double l);*)
> let t1 =3D Sys.time() in ignore ();(*(ExtLib.List.unique l);*)
> let t2 =3D Sys.time() in Gc.compact ();
> (*let t3 =3D Sys.time() in ignore (ExtLib.List.unique l);*)
> let t3 =3D Sys.time() in ignore (delete_double_unsort l);
> let t4 =3D Sys.time() in
> (t2-.t1,t4-.t3)
> in
> let rec make_bench r n p =3D
> if p =3D=3D 0 then r else make_bench ((a_bench n)::r) n (pred p)
> in
> let somme r =3D
> let a,b =3D List.split r in
> List.fold_left (+.) 0. a, List.fold_left (+.) 0. b
> in
> let t1,t2 =3D somme (make_bench [] n p) in
> Printf.printf "\n[%.3f] [%.3f]\n" t1 t2
> ;;
> bench (int_of_string Sys.argv.(1)) (int_of_string Sys.argv.(2))
> *)
> (*
> let verif n =3D
> Random.self_init();
> let rec new_list n =3D
> if n =3D=3D 0 then [] else ( Random.int <http://Random.int> 10)::(new_lis=
t
> (pred n))
> in
> let test l =3D
> let p l =3D List.iter (Printf.printf "%d ") l in
> (* p l ;print_newline (); *)
> let l1 =3D delete_double_unsort_list ~last:true l
> and l2 =3D delete_double_unsort ~last:true l
> and l3 =3D ExtLib.List.unique l
> in
> (* p l1;print_newline ();
> p l2;print_newline ();
> p l3;print_newline (); *)
> (l1 =3D l2 && l1 =3D l3)
> in
> while (test (new_list n)) do (); done
> ;;
> verif (int_of_string Sys.argv.(1));;
> *)
>
>
>
>
>
>
>
> _________________________________________________________________________=
__
> Appel audio GRATUIT partout dans le monde avec le nouveau Yahoo! Messenge=
r
>
> T=E9l=E9chargez cette version sur http://fr.messenger.yahoo.com
>
>
>
> -------------------------------------------------------
> This SF.Net email is sponsored by:
> Power Architecture Resource Center: Free content, downloads, discussions,
> and more. http://solutions.newsforge.com/ibmarch.tmpl
> _______________________________________________
> ocaml-lib-devel mailing list
> oca...@li...
> https://lists.sourceforge.net/lists/listinfo/ocaml-lib-devel
>

[Ocaml-lib-devel] Extlib.list.unique

[sejourne_kevin <sej...@ya...>]

Hello evrybody.

Thanks for that lib I use evryday.

But, I notice that ExtList.unique is in O(n^2) this is a problem for me,
I often use list over 100000 elements(and some time over million).
So I wrote a replacement function that is faster O(n+n*log(n)).
It use about 5X the space of the parameter list. On my computer (512 Mo)
the limit before the stak overflow is just over a million.


let delete_double_unsort ?(last=false) ?(cmp=Pervasives.compare) l =
  let lg = List.length l in
      let tcn = Array.make lg (List.hd l,0) in
      let rec add_num n = function
	  [] -> ()
	| h :: t -> tcn.(n) <- (h,n) ; (add_num (succ n) t)
      in
      let () = add_num 0 l in
      let compare x y = cmp (fst x) (fst y) in
      let tcn' = Array.copy tcn in
      let () = Array.stable_sort compare tcn in
      let plg = lg -1 in
      let rec get_dbl ac n =
	if n == plg then ac
	else
	  let n' = n+1 in
	  let h1 = tcn.(n) in
	  let h2 = tcn.(n') in
	  if (cmp (fst h1) (fst h2)) == 0
	  then get_dbl ((snd (if last then h1 else h2))::ac) n'
	  else get_dbl ac n'
      in
      let dbl = get_dbl [] 0 in
      let sdbl = List.sort Pervasives.compare dbl in
      let rec delete n = function
	  [] ->
	    let ac = ref [] in
	    for i = n to lg -1 do
	      ac := (fst tcn'.(i)) :: !ac
	    done;
	    List.rev !ac
	| na::ta when na == (snd tcn'.(n)) -> delete (n+1) ta
	| l ->  (fst tcn'.(n)) :: (delete (n+1) l)
      in delete 0 sdbl
;;

As you can see this function support a additionnal option that let you
select if you want delete the first or the last occurence of a term.
For the "equivalence" with ExtList.unique set "~last:true".


for 100000 elements :
Extlib.list.unique : 165.850 seconds
this function : 0.380 seconds
for 1000000 elements :
Extlib.list.unique : stop by error after 2 hours...
this function : 9.600 seconds



Even if you don't want to include it in the ExtLib I would be glade if
someone know how to improve it.



Here few test code:
(*
let bench n p =
  Random.self_init();
  let rec new_list n =
    if n == 0 then [] else (Random.int 100000)::(new_list (pred n))
  in
  let a_bench n =
    let l  = new_list n in Gc.compact();
    (*let t1 = Sys.time() in  ignore (delete_double_unsort_list l);*)
    (*let t1 = Sys.time() in  ignore (delete_double l);*)
    let t1 = Sys.time() in ignore ();(*(ExtLib.List.unique l);*)
    let t2 = Sys.time() in Gc.compact();
    (*let t3 = Sys.time() in ignore (ExtLib.List.unique l);*)
    let t3 = Sys.time() in ignore (delete_double_unsort l);
    let t4 = Sys.time() in
     (t2-.t1,t4-.t3)
  in
  let rec make_bench r n p =
    if p == 0 then r else make_bench ((a_bench n)::r) n (pred p)
  in
  let somme r =
    let a,b = List.split r in
      List.fold_left (+.) 0. a, List.fold_left (+.) 0. b
  in
  let t1,t2 = somme (make_bench [] n p) in
    Printf.printf "\n[%.3f] [%.3f]\n" t1 t2
;;
bench (int_of_string Sys.argv.(1)) (int_of_string Sys.argv.(2))
*)
(*
let verif n =
  Random.self_init();
  let rec new_list n =
    if n == 0 then [] else (Random.int 10)::(new_list (pred n))
  in
  let test l =
    let p l =  List.iter (Printf.printf "%d ") l in
   (*   p l ;print_newline (); *)
    let l1 = delete_double_unsort_list ~last:true l
    and l2 = delete_double_unsort ~last:true l
    and l3 = ExtLib.List.unique l
    in
 (*   p l1;print_newline ();
    p l2;print_newline ();
    p l3;print_newline (); *)
    (l1 = l2 && l1 = l3)
  in
    while (test (new_list n)) do (); done
;;
verif (int_of_string Sys.argv.(1));;
*)


	

	
		
___________________________________________________________________________ 
Appel audio GRATUIT partout dans le monde avec le nouveau Yahoo! Messenger 
Téléchargez cette version sur http://fr.messenger.yahoo.com

Re: [Ocaml-lib-devel] List

[Richard J. <ri...@an...>]

On Sun, Oct 02, 2005 at 08:56:05PM -0500, Brian Hurt wrote:
> That was the behavior of those functions in the standard library. 
> Basically, the contact was that the code should behave identically, just 
> faster.  I.e. if the standard library threw a given exception in a given 
> case, ExtLib would throw the exact same exception.  This allows ExtLib to 
> be a drop-in replacement for the standard library.

Although not always, cf. List.sort / ExtList.List.sort.

Rich.

-- 
Richard Jones, CTO Merjis Ltd.
Merjis - web marketing and technology - http://merjis.com
Team Notepad - intranets and extranets for business - http://team-notepad.com

Re: [Ocaml-lib-devel] Installing Extlib

[Amit D. <ami...@gm...>]

You'll need to install ocamlfind.

Documentation is here:
http://www.ocaml-programming.de/packages/documentation/findlib/

Download from here:
http://www.ocaml-programming.de/packages/findlib-1.0.4.tar.gz

This information (with links) should probably be added to the Extlib
webpage. Nicolas: could you either add this information, or add group write
permission (+sticky?) to the htdocs directory?

Thanks,
-Amit

On 10/3/05, Bill Wood <wil...@co...> wrote:
>
> When I ran "ocaml install.ml <http://install.ml>" I was informed that
> "ocamlfind" wasn't
> found. That entry is not in /usr/local/bin along with the rest of the
> ocaml entry points, nor anyplace else according to which. Should I have
> it? If so, where do I get it? BTW, I recently installed OCaml 3.08.3.
>
> Also, if I want ocaml to find the extlib modules, where should I
> install?
>
> Many thanks,
>
> -- Bill Wood
>
>
>
>
> -------------------------------------------------------
> This SF.Net email is sponsored by:
> Power Architecture Resource Center: Free content, downloads, discussions,
> and more. http://solutions.newsforge.com/ibmarch.tmpl
> _______________________________________________
> ocaml-lib-devel mailing list
> oca...@li...
> https://lists.sourceforge.net/lists/listinfo/ocaml-lib-devel
>

Re: [Ocaml-lib-devel] Dllist skip negative arguments

[Amit D. <ami...@gm...>]

Good point. I'll use this version. Hmmm... maybe I should add a unit test
for skip as well...

-Amit

On 10/4/05, Brian Hurt <bh...@sp...> wrote:
>
>
>
> On Tue, 4 Oct 2005, Amit Dubey wrote:
>
> > Looking at Dllist.skip, this looks like a bug. A better implementation
> of
> > skip might be:
> >
> > let skip node idx =3D
> > let rec loop idx n =3D
> > if idx =3D=3D 0 then
> > n
> > else if idx>0 then
> > loop (idx -1) n.next
> > else
> > loop (idx + 1) n.prev
> > in
> > loop idx node
> >
> > (The current version doesn't use n.prev for negative arguments). If
> there
> > are no complains, I'll make this change.
>
> I'm wondering if it might not be better to split the two loops, to avoid
> taking repeated branchs:
>
> let skip node idx =3D
> let rec floop idx n =3D
> if idx =3D=3D 0 then
> n
> else
> floop (idx-1) n.next
> in
> let rec bloop idx n =3D
> if idx =3D=3D 0 then
> n
> else
> bloop (idx-1) n.prev
> in
> if idx =3D=3D 0 then
> n
> else if idx > 0 then
> floop (idx-1) n.next
> else
> bloop ((-idx)-1) n.prev
> ;;
>
> Brian
>
>

Re: [Ocaml-lib-devel] Dllist skip negative arguments

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

On Tue, 4 Oct 2005, Amit Dubey wrote:

> Looking at Dllist.skip, this looks like a bug. A better implementation of
> skip might be:
>
> let skip node idx =
> let rec loop idx n =
> if idx == 0 then
> n
> else if idx>0 then
> loop (idx -1) n.next
> else
> loop (idx + 1) n.prev
> in
> loop idx node
>
> (The current version doesn't use n.prev for negative arguments). If there
> are no complains, I'll make this change.

I'm wondering if it might not be better to split the two loops, to avoid 
taking repeated branchs:

let skip node idx =
 	let rec floop idx n =
 		if idx == 0 then
 			n
 		else
 			floop (idx-1) n.next
 	in
 	let rec bloop idx n =
 		if idx == 0 then
 			n
 		else
 			bloop (idx-1) n.prev
 	in
 	if idx == 0 then
 		n
 	else if idx > 0 then
 		floop (idx-1) n.next
 	else
 		bloop ((-idx)-1) n.prev
;;

Brian

Re: [Ocaml-lib-devel] Dllist skip negative arguments

[Amit D. <ami...@gm...>]

Looking at Dllist.skip, this looks like a bug. A better implementation of
skip might be:

let skip node idx =3D
let rec loop idx n =3D
if idx =3D=3D 0 then
n
else if idx>0 then
loop (idx -1) n.next
else
loop (idx + 1) n.prev
in
loop idx node

(The current version doesn't use n.prev for negative arguments). If there
are no complains, I'll make this change.



On 10/3/05, Pierre-Antoine Delsart <de...@lp...> wrote:
>
>
> Hello people,
>
> Is it normal that I can't have Dllist.skip work as I expect using
> negative arguments ?
>
> Here is an exemple of what I'm trying with extlib 1.4 :
>
> > ocaml -I /<path_to_extlib>/ /<path_to_extlib>/extLib.cma
>
> let ll =3D Dllist.create 0;;
> Dllist.add ll 4;;
> Dllist.add ll 8;;
> Dllist.add ll 5012;;
> let printl a =3D print_string ((string_of_int a)^"\n");;
> Dllist.iter printl ll;;
> let ll1 =3D Dllist.skip ll 1;;
> Dllist.iter printl ll1;;
> let ll1m =3D Dllist.skip ll (-1);;
> Dllist.iter printl ll1m;;
>
>
> I expect the operation on ll1 and ll1m to behave differently, however I
> have exactly the same result ... as if the negative sign was not taken
> into account.
>
> Am I doing something wrong ?
>
> Thanks for your help.
>
> PA.
>
>
> -------------------------------------------------------
> This SF.Net email is sponsored by:
> Power Architecture Resource Center: Free content, downloads, discussions,
> and more. http://solutions.newsforge.com/ibmarch.tmpl
> _______________________________________________
> ocaml-lib-devel mailing list
> oca...@li...
> https://lists.sourceforge.net/lists/listinfo/ocaml-lib-devel
>

[Ocaml-lib-devel] Dllist skip negative arguments

[Pierre-Antoine D. <de...@LP...>]

Hello people,

Is it normal that I can't have Dllist.skip work as I expect using 
negative arguments ?

Here is an exemple of what I'm trying with extlib 1.4 :

 > ocaml  -I /<path_to_extlib>/ /<path_to_extlib>/extLib.cma

let ll = Dllist.create 0;;
Dllist.add ll 4;;
Dllist.add ll 8;;
Dllist.add ll 5012;;
let printl a = print_string ((string_of_int a)^"\n");;
Dllist.iter printl ll;;
let ll1 = Dllist.skip ll 1;;
Dllist.iter printl ll1;;
let ll1m = Dllist.skip ll (-1);;
Dllist.iter printl ll1m;;


I expect the operation on ll1 and ll1m to behave differently, however I 
have exactly the same result ... as if the negative sign was not taken 
into account.

Am I doing something wrong ?

Thanks for your help.

PA.

Re: [Ocaml-lib-devel] Enum

[Bill W. <wil...@co...>]

   . . .
> It's more like a lazy sequence. Since it's lazy, it can be infinite if you
> define a "next" function always returning an element. But it's consuming so
> when enumerating "append e e" you first consume "e" and then "e" is empty,
> so it's not circular.

It seems very similar to Scheme streams implemented by means of "delay"
and "force", yes?

Thanks,

 -- Bill Wood

Re: [Ocaml-lib-devel] Enum

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

> What exactly *is* an enum?  Is it a lazy list?  sequence? totally
> ordered multiset?

It's more like a lazy sequence. Since it's lazy, it can be infinite if you
define a "next" function always returning an element. But it's consuming so
when enumerating "append e e" you first consume "e" and then "e" is empty,
so it's not circular.

Nicolas

[Ocaml-lib-devel] Installing Extlib

[Bill W. <wil...@co...>]

When I ran "ocaml install.ml" I was informed that "ocamlfind" wasn't
found.  That entry is not in /usr/local/bin along with the rest of the
ocaml entry points, nor anyplace else according to which.  Should I have
it?  If so, where do I get it?  BTW, I recently installed OCaml 3.08.3.

Also, if I want ocaml to find the extlib modules, where should I
install?

Many thanks,

 -- Bill Wood

Re: [Ocaml-lib-devel] List

[Bill W. <wil...@co...>]

   . . .
> That was the behavior of those functions in the standard library. 
> Basically, the contact was that the code should behave identically, just 
> faster.  I.e. if the standard library threw a given exception in a given 
> case, ExtLib would throw the exact same exception.  This allows ExtLib to 
> be a drop-in replacement for the standard library.

OK, that's sensible under those conditions.  Guess I need to pick on the
standard lib folks, right? :-)

 -- Bill Wood

Re: [Ocaml-lib-devel] List

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

On Sun, 2 Oct 2005, Bill Wood wrote:

> (Hi, it's me again :-)  Is there a compelling reason why map2, iter2,
> fold_left2, fold_right2, for_all2, exists2 and combine require their two
> list arguments to be of the same length?  Analogous functions in Common
> Lisp, Haskell and SML (zip vs zipEq) don't make that restriction.

That was the behavior of those functions in the standard library. 
Basically, the contact was that the code should behave identically, just 
faster.  I.e. if the standard library threw a given exception in a given 
case, ExtLib would throw the exact same exception.  This allows ExtLib to 
be a drop-in replacement for the standard library.

Brian

[Ocaml-lib-devel] List

[Bill W. <wil...@co...>]

(Hi, it's me again :-)  Is there a compelling reason why map2, iter2,
fold_left2, fold_right2, for_all2, exists2 and combine require their two
list arguments to be of the same length?  Analogous functions in Common
Lisp, Haskell and SML (zip vs zipEq) don't make that restriction.

Thanks,

 -- Bill Wood
    bil...@ac...

[Ocaml-lib-devel] Enum

[Bill W. <wil...@co...>]

What exactly *is* an enum?  Is it a lazy list?  sequence? totally
ordered multiset?

Can an enum be (potentially) infinite?  For example, what does
    let e = Extlib.Enum,make my_next my_count my_clone in
      Extlib.Enum,append e e
return?  NOTE:
    let x = my_list in x @ x
returns a circular list.  I'm curious as to whether a similar concept
exists with enums.

Thanks,

 -- Bill Wood
    bil...@ac...

Re: [Ocaml-lib-devel] ExtList.findi

[Richard J. <ri...@an...>]

On Fri, Sep 09, 2005 at 12:16:21PM +0100, Amit Dubey wrote:
> val findi : (int -> 'a -> bool) -> 'a list -> (int * 'a)
> (** [findi p e l] returns the first element [ai] of [l] along with its
> index [i] such that [p i ai] is true, or raises [Not_found] if no
> such element has been found. *)

I think it's a great idea.

Rich.

-- 
Richard Jones, CTO Merjis Ltd.
Merjis - web marketing and technology - http://merjis.com
Team Notepad - intranets and extranets for business - http://team-notepad.com

[Ocaml-lib-devel] ExtList.findi

[Amit D. <ami...@gm...>]

Hi,

I was surprised to find there is no findi function in ExtLib. I'm=20
considering adding:

to extList.ml:

let rec findi p l =3D
let rec loop n =3D function
| [] -> raise Not_found
| h :: t ->
if p n h then (n,h) else loop (n+1) t
in
loop 0 l

to extList.mli:

val findi : (int -> 'a -> bool) -> 'a list -> (int * 'a)
(** [findi p e l] returns the first element [ai] of [l] along with its
index [i] such that [p i ai] is true, or raises [Not_found] if no
such element has been found. *)

I still have CVS access, if there are no complaints, I will submit this in =
a=20
couple days.

Re: [Ocaml-lib-devel] Unzip Module

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

> Hi,
>
> How come you didn't add Zip as well? That would've been a useful
> addition to have.
>
> Jonathan

It's a bit more difficult to do and I didn't have time to write it.
However since Unzip provide some useful data structures such as reduced
Huffman tree, you're welcome to contribute it :)

Nicolas

[Ocaml-lib-devel] Unzip Module

[Jonathan R. <jon...@gm...>]

Hi,

How come you didn't add Zip as well? That would've been a useful
addition to have.

Jonathan

[Ocaml-lib-devel] Re: List.map_pairs

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

In article <200...@fu...>, Richard Jones wrote:
> On Wed, Aug 10, 2005 at 06:34:19PM +0000, Alan Post wrote:
>> In article <200...@fu...>, Richard W. M. Jones wrote:
>> > 
>> > Well OK, but we don't even have a function to do the
>> > int list -> (int * int) list transformation.
>> 
>> A fold using a ref would work, yes?
> 
> Something like that might, but the whole point of HOFs is to avoid
> having to write ugly hacks all the time :-)

OK, here's a tail-recursive function using a fold without a ref:

let take_pairs =
  let f (i,l) j = (j, (i,j)::l)
  in function
  | [] -> []
  | h::tl -> List.rev (snd (List.fold_left f (h, []) tl))

Re: [Ocaml-lib-devel] Re: List.map_pairs

[Richard J. <ri...@an...>]

On Wed, Aug 10, 2005 at 06:34:19PM +0000, Alan Post wrote:
> In article <200...@fu...>, Richard W. M. Jones wrote:
> > 
> > Well OK, but we don't even have a function to do the
> > int list -> (int * int) list transformation.
> 
> A fold using a ref would work, yes?

Something like that might, but the whole point of HOFs is to avoid
having to write ugly hacks all the time :-)

Here are my two functions for taking pairs of elements from lists.
FWIW, I have used both of these patterns in real code on more than one
occasion, although the first one is used a lot more frequently than
the second (for disaggregating our counted data):

# let rec take_pairs = function
  | [] | [_] -> invalid_arg "take_pairs"
  | [x; y] -> [x, y]
  | x :: (y :: _ as xs) ->
    (x, y) :: take_pairs xs;;
val take_pairs : 'a list -> ('a * 'a) list = <fun>
# take_pairs [1; 2; 3; 4; 5; 6; 7; 8];;
- : (int * int) list =
[(1, 2); (2, 3); (3, 4); (4, 5); (5, 6); (6, 7); (7, 8)]

# let rec take_in_twos = function
  | [] -> []
  | [_] -> invalid_arg "take_in_twos"
  | x :: y :: xs -> (x, y) :: take_in_twos xs;;
val take_in_twos : 'a list -> ('a * 'a) list = <fun>
# take_in_twos [1; 2; 3; 4; 5; 6; 7; 8];;
- : (int * int) list = [(1, 2); (3, 4); (5, 6); (7, 8)]

Rich.

-- 
Richard Jones, CTO Merjis Ltd.
Merjis - web marketing and technology - http://merjis.com
Team Notepad - intranets and extranets for business - http://team-notepad.com

Re: [Ocaml-lib-devel] Proposal for new list functions

[Janne H. <jjh...@gm...>]

>     The proposed separate function is doing the opposite of concatentatio=
n,
> so how about called it List.decatenate?  It is admitedly a wierd name,
> but it gets the meaning across and is reasonably specific: if you
> understand list concatentation, you'll have a general idea of what
> decatenate ought to do.

It's a bit strange name, but I like it!  It must be said though that=20

"concat (decatenate p lst)"

does not equal to the original list as elements satisfying predicate p
are thrown away.

String.concat takes an additional parameter that is inserted between
the concatenated elements.  I would find such a functionality useful
lists too.

Best regards,
Janne

Re: [Ocaml-lib-devel] Proposal for new list functions

[Amit D. <ad...@Co...>]

    The proposed separate function is doing the opposite of concatentation,
so how about called it List.decatenate?  It is admitedly a wierd name,
but it gets the meaning across and is reasonably specific: if you
understand list concatentation, you'll have a general idea of what
decatenate ought to do.

    -Amit

> 
> On 8/11/05, Nicolas Cannasse <war...@fr...> wrote:
> > > val fold_left_while :
> > >    ('a -> 'b -> bool) -> ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a = <fun>
> > 
> > I think too that having an exception is better than providing two functions.
> > 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 group
> > both test+fold into a single function since I can't see good cases when you
> > 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.  
> 
> 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 = <fun>
> > 
> > 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 = <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 =
>   let rec loop acc = function
>       [] -> (acc,[])
>     | (x::xs) as rest ->
>         if pred x then (acc, rest) else loop (x::acc) xs in
>   let (start,rest) = 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 = <fun>
> 
> (** [separate p l] splits list [l] into sublists that do not contain
>     elements satisfying [p x] predicate. Example: 
>     [separate (fun c -> c = '\n') ['a'; 'b'; '\n'; 'c']] yields 
>     [[['a'; 'b']; ['c']]] *)
> let separate pred lst = 
>   let rec loop acc lst = 
>     let (start,rest) = split_when pred lst in
>     let acc' = 
>       if start = [] 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 = '\n') ['a'; 'b'; '\n'; 'c'];;
> - : char list list = [['a'; 'b']; ['c']]
> # separate ((=) 0) [];;
> - : int list list = []
> # separate ((=) 0) [0];;
> - : int list list = []
> # separate ((=) 0) [1; 2; 3; 0; 4; 5; 6; 7; 0];;
> - : int list list = [[1; 2; 3]; [4; 5; 6; 7]]
> # separate ((=) 0) [0; 4; 5; 6; 7; 0];;
> - : int list list = [[4; 5; 6; 7]]
> # separate ((=) 0) [0; 4; 5; 6; 7; 0; 33];;
> - : int list list = [[4; 5; 6; 7]; [33]]
> # separate ((=) 0) [0; 0; 0];;
> - : int list list = []
> 
> Best regards,
> Janne
> 
> 
> -------------------------------------------------------
> SF.Net email is Sponsored by the Better Software Conference & EXPO
> September 19-22, 2005 * San Francisco, CA * Development Lifecycle Practices
> Agile & Plan-Driven Development * Managing Projects & Teams * Testing & QA
> Security * Process Improvement & Measurement * http://www.sqe.com/bsce5sf
> _______________________________________________
> ocaml-lib-devel mailing list
> oca...@li...
> https://lists.sourceforge.net/lists/listinfo/ocaml-lib-devel
> 

Re: [Ocaml-lib-devel] Proposal for new list functions

[Janne H. <jjh...@gm...>]

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

[Ocaml-lib-devel] Re: List.map_pairs

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

In article <200...@fu...>, Richard W. M. Jones wrote:
> 
> Well OK, but we don't even have a function to do the
> int list -> (int * int) list transformation.

A fold using a ref would work, yes?