[Caml-list] Are map and iter guaranteed to be called in forwards order?

[Caml-list] Are map and iter guaranteed to be called in forwards order?

[Richard Jones]

Are the map and iter[1] functions guaranteed to be called in the
expected order?  In other words will this always produce the same
result:

# let i = ref 0 ;;
val i : int ref = {contents = 0}
# let xs = List.map (fun _ -> incr i; !i) [ 1;1;1;1;1;1;1;1 ];;
val xs : int list = [1; 2; 3; 4; 5; 6; 7; 8]

Rich.

[1] From List, for example, but could equally apply to the other
library modules.

-- 
Richard Jones. http://www.annexia.org/ http://www.j-london.com/
Merjis Ltd. http://www.merjis.com/ - improving website return on investment
NET::FTPSERVER is a full-featured, secure, configurable, database-backed
FTP server written in Perl: http://www.annexia.org/freeware/netftpserver/

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Are map and iter guaranteed to be called in forwards order?

[Damien Doligez]

On Aug 17, 2004, at 14:00, Richard Jones wrote:

> Are the map and iter[1] functions guaranteed to be called in the
> expected order?

iter: yes
map: no

-- Damien

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Are map and iter guaranteed to be called in forwards order?

[John Prevost]

On Tue, 17 Aug 2004 13:00:53 +0100, Richard Jones <rich@annexia.org> wrote:
> Are the map and iter[1] functions guaranteed to be called in the
> expected order?  In other words will this always produce the same
> result:
  {...}
> [1] From List, for example, but could equally apply to the other
> library modules.

You should also note that both map and iter can sensibly be provided
for data structures that don't have any strong guarantee of order at
all.  For example, a set.  As a rule of thumb, I'd say it's best not
to depend on order in these calls unless (perhaps) you have
implemented the routine yourself, or are using a library that
specifically says what order the calls will be processed.

As Damien says, the documentation for List.map makes no guarantee of
order, while List.iter's documentation says that it is identical to
another construct that does guarantee order.

John.

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Are map and iter guaranteed to be called in forwards order?

[Richard Jones]

This came up because I wanted a sensible way to number a list of
items.  The obvious imperative approach is:

  # let items = ['a';'c';'e';'g';'i'];;
  val items : char list = ['a'; 'c'; 'e'; 'g'; 'i']
  # let i = ref 0;;
  val i : int ref = {contents = 0}
  # let items = List.map (fun item -> let n = !i in incr i; n, item) items;;
  val items : (int * char) list =
    [(0, 'a'); (1, 'c'); (2, 'e'); (3, 'g'); (4, 'i')]

The functional approach is comparatively long-winded: you have to
effectively write your own loop explicitly, and the obvious way to
write it isn't tail recursive, so you have to do it with accumulators.

It'd be nicer to have a library HOF to do this.

Rich.

-- 
Richard Jones. http://www.annexia.org/ http://www.j-london.com/
Merjis Ltd. http://www.merjis.com/ - improving website return on investment
MOD_CAML lets you run type-safe Objective CAML programs inside the Apache
webserver. http://www.merjis.com/developers/mod_caml/

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Are map and iter guaranteed to be called in forwards order?

[Anil Madhavapeddy]

On Tue, Aug 17, 2004 at 03:56:53PM +0100, Richard Jones wrote:
> This came up because I wanted a sensible way to number a list of
> items.  The obvious imperative approach is:
> 
>   # let items = ['a';'c';'e';'g';'i'];;
>   val items : char list = ['a'; 'c'; 'e'; 'g'; 'i']
>   # let i = ref 0;;
>   val i : int ref = {contents = 0}
>   # let items = List.map (fun item -> let n = !i in incr i; n, item) items;;
>   val items : (int * char) list =
>     [(0, 'a'); (1, 'c'); (2, 'e'); (3, 'g'); (4, 'i')]
> 
> The functional approach is comparatively long-winded: you have to
> effectively write your own loop explicitly, and the obvious way to
> write it isn't tail recursive, so you have to do it with accumulators.
> 

Would List.combine come in handy?

Something like:

# let rec numlist n a = match n with |0 -> a |x -> numlist (n-1) (x::a);;
val numlist : int -> int list -> int list = <fun>
# let number l = List.combine (numlist (List.length l) []) l;;
val number : 'a list -> (int * 'a) list = <fun>
# let items = ['a';'c';'e';'g';'i'];;
val items : char list = ['a'; 'c'; 'e'; 'g'; 'i']
# number items;;                                       
- : (int * char) list = [(1, 'a'); (2, 'c'); (3, 'e'); (4, 'g'); (5, 'i')]

-- 
Anil Madhavapeddy                                 http://anil.recoil.org
University of Cambridge                          http://www.cl.cam.ac.uk

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Are map and iter guaranteed to be called in forwards order?

[Jean-Marie Gaillourdert]

Hi,

Am Dienstag, 17. August 2004 16:56 schrieb Richard Jones:
> This came up because I wanted a sensible way to number a list of
> items.  The obvious imperative approach is:
>
>   # let items = ['a';'c';'e';'g';'i'];;
>   val items : char list = ['a'; 'c'; 'e'; 'g'; 'i']
>   # let i = ref 0;;
>   val i : int ref = {contents = 0}
>   # let items = List.map (fun item -> let n = !i in incr i; n, item)
> items;; val items : (int * char) list =
>     [(0, 'a'); (1, 'c'); (2, 'e'); (3, 'g'); (4, 'i')]
>
> The functional approach is comparatively long-winded: you have to
> effectively write your own loop explicitly, and the obvious way to
> write it isn't tail recursive, so you have to do it with accumulators.
>
> It'd be nicer to have a library HOF to do this.

There is a higher order function to do this: fold

List.rev 
  (List.fold_left (fun xs x -> 
    match xs with 
      [] -> [(0,x)] 
    | (i,_)::_ -> (i+1,x)::xs) [] items);;

Regards,
  Jean-Marie

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Are map and iter guaranteed to be called in forwards order?

[John Prevost]

On Tue, 17 Aug 2004 15:56:53 +0100, Richard Jones <rich@annexia.org> wrote:
> This came up because I wanted a sensible way to number a list of
> items.  The obvious imperative approach is:
> 
>   # let items = ['a';'c';'e';'g';'i'];;
>   val items : char list = ['a'; 'c'; 'e'; 'g'; 'i']
>   # let i = ref 0;;
>   val i : int ref = {contents = 0}
>   # let items = List.map (fun item -> let n = !i in incr i; n, item) items;;
>   val items : (int * char) list =
>     [(0, 'a'); (1, 'c'); (2, 'e'); (3, 'g'); (4, 'i')]
> 
> The functional approach is comparatively long-winded: you have to
> effectively write your own loop explicitly, and the obvious way to
> write it isn't tail recursive, so you have to do it with accumulators.
> 
> It'd be nicer to have a library HOF to do this.

How about fold?

let number l =
  let _, l = List.fold_left (fun (n, l) i -> (n+1, (n, i)::l)) (0, []) l in
  List.rev l

You could even do fold with side effects if you really want to:

let number' l =
  let i = ref 0 in
  let l = List.fold_left (fun l x -> let n = !i in incr i; (n, x) :: l) [] l in
  List.rev l

Or define your own version of map, that you have explicitly written to
be based on fold_left, which allows you to be sure that it will always
work the same way:

let folding_map f l =
  let l = List.fold_left (fun l x -> (f x)::l) [] l in
  List.rev l

John.

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Are map and iter guaranteed to be called in forwards order?

[Jon Harrop]

On Tuesday 17 August 2004 15:26, John Prevost wrote:
> You should also note that both map and iter can sensibly be provided
> for data structures that don't have any strong guarantee of order at
> all.  For example, a set...

That is so nineties. Someone at INRIA kindly changed this of late (3.08) - The 
set and map data structures do now guarantee element order.

On Tuesday 17 August 2004 16:13, Anil Madhavapeddy wrote:
> # let rec numlist n a = match n with |0 -> a |x -> numlist (n-1) (x::a);;
> val numlist : int -> int list -> int list = <fun>
> ...

This would work but I think we can do better. Deforesting is a good start - we 
don't want lots of big data structures cluttering up the place...

On Tuesday 17 August 2004 16:17, Jean-Marie Gaillourdert wrote:
> List.rev
>   (List.fold_left (fun xs x ->
>     match xs with
>       [] -> [(0,x)]
>     | (i,_)::_ -> (i+1,x)::xs) [] items);;

That's good, but it's no hot potato. Using fold is a great idea, IMHO. The 
List.fold_left function is preferable to List.fold_right because the former 
is tail-recursive and, therefore, will be much faster for big lists. But we 
can do more to get rid of the pattern matching - we can fold over a 2-tuple 
which accumulates the current index and the current list (in reverse order):

On Tuesday 17 August 2004 16:19, John Prevost wrote:
> let number l =
>   let _, l = List.fold_left (fun (n, l) i -> (n+1, (n, i)::l)) (0, []) l in
>   List.rev l
> ...

Almost there, me thinks. You can tweak this one by using the "snd" function to 
rip out the second half of the 2-tuple, rather than using pattern matching, 
squeezing the whole function into a slender pair of lines:

let index l =
  List.rev (snd (List.fold_left (fun (i, l) e -> i+1, (i, e)::l) (0, []) l));;

If you're feeling really adventurous, you can factor the algorithm agressively 
(grrr!), producing many useful functions at intermediate stages. Essentially, 
we've been folding over one data structure, handling the index and the 
element, and inserting into another data structure given a value representing 
the empty data structure. We could productively generalise this to a function 
with an outrageous type:

# let generic_mapi fold insert empty t =
    snd (fold (fun (i, l) e -> i+1, insert (i, e) l) (0, empty) t);;
val generic_mapi :
  ((int * 'a -> 'b -> int * 'c) -> int * 'd -> 'e -> 'f * 'g) ->
  (int * 'b -> 'a -> 'c) -> 'd -> 'e -> 'g = <fun>

First, let us use the generic_mapi function to create a HOF list_rev_mapi 
which does a List.rev_map of a given function applied to the index as well as 
the value of each element in the given list:

# let list_rev_mapi f l =
    (generic_mapi List.fold_left (fun (i, e) t -> f i e :: t) [] l);;
val list_rev_mapi : (int -> 'a -> 'b) -> 'a list -> 'b list = <fun>

This function can then be used to create your function to convert a list into 
an indexed list by passing a function which creates an index-value 2-tuple to 
our list_rev_mapi HOF and reversing its result:

# let ilist_of_list l = List.rev (list_rev_mapi (fun i e -> i, e) l);;
val ilist_of_list : 'a list -> (int * 'a) list = <fun>
# ilist_of_list ['a'; 'c'; 'e'; 'g'; 'i'];;
- : (int * char) list = [(0, 'a'); (1, 'c'); (2, 'e'); (3, 'g'); (4, 'i')]

The following, nifty HOF converts left fold types into right fold types and 
vice versa:

# let rev_fold fold f a b = fold (fun a b -> f b a) b a;;
val rev_fold :
  (('a -> 'b -> 'c) -> 'd -> 'e -> 'f) -> ('b -> 'a -> 'c) -> 'e -> 'd -> 'f =
  <fun>

This rev_fold function can be used with our (stupendously generic) 
generic_mapi function to index the elements of a set of chars, placing the 
result in a hash table mapping chars to indices:

# module CharKey = struct type t=char let compare = compare end;;
module CharKey : sig type t = char val compare : 'a -> 'a -> int end
# module CharSet = Set.Make(CharKey);;
...
# let piece_of_cake s =
  let h = Hashtbl.create (CharSet.cardinal s) in
  let fold = rev_fold CharSet.fold in
  generic_mapi fold (fun (i, e) () -> Hashtbl.add h e i) () s;
  h;;
val piece_of_cake : CharSet.t -> (CharSet.elt, int) Hashtbl.t = <fun>

For example:

# let set_of s =
    let set = ref CharSet.empty in
    String.iter (fun c -> set := CharSet.add c !set) s;
    !set;;
val set_of : string -> CharSet.t = <fun>
# let test_set = set_of "The wagged wascle wan wound the wugged wock";;
val test_set : CharSet.t = <abstr>
# let test_table = piece_of_cake test_set;;
val test_table : (CharSet.elt, int) Hashtbl.t = <abstr>
# Hashtbl.find test_table 'g';;
- : int = 9

So thirteen characters in the ASCII alphabet came after 'a' in our string.

Ha! Try writing that in Felix (in another mailing-list, of course ;-).

Cheers,
Jon.

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Are map and iter guaranteed to be called in forwards order?

[skaller]

On Wed, 2004-08-18 at 10:57, Jon Harrop wrote:
> On Tuesday 17 August 2004 15:26, John Prevost wrote:

> let index l =
>   List.rev (snd (List.fold_left (fun (i, l) e -> i+1, (i, e)::l) (0, []) l));;

> Ha! Try writing that in Felix (in another mailing-list, of course ;-).

Unfair to make that challange and deny the right to a response :)
So you get it: its much the same as the Caml version except
the type annotations on the arguments are mandatory in Felix:

fun index[t] (l:list[t]) =>
  rev (snd (
    fold_left
      (fun (i:int, l: list [t], e: int * t) =>
        i+1, Cons ((i, e),l)
      )
      (0, Empty[t]) 
      l
  ))
;

The actual code above doesn't compile due to a bug,
so I'm glad of the example -- thanks! [Looks like
I forgot to alpha convert before unifying during
overload resolution]

However its *should* work: What Caml can do and Felix cannot, 
is pass a *polymorphic* function as an argument. Caml allows
that -- but then you can only use it monomorphically 
[unless you wrap it in a record].

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Are map and iter guaranteed to be called in forwards order?

[skaller]

On Wed, 2004-08-18 at 15:11, skaller wrote:
> On Wed, 2004-08-18 at 10:57, Jon Harrop wrote:
> > On Tuesday 17 August 2004 15:26, John Prevost wrote:
> 
> > let index l =
> >   List.rev (snd (List.fold_left (fun (i, l) e -> i+1, (i, e)::l) (0, []) l));;
> 
> > Ha! Try writing that in Felix (in another mailing-list, of course ;-).
> 
> The actual code above doesn't compile due to a bug,

Oops. Its a bug in my translation of the routine, not in Felix!
The code below actually works. Clear advantages of Ocaml here are:

(a) Ocaml's type inference simplifies presentation
  
(b) :: as both constructor and pattern in Ocaml are nice,
   as is [x;y;z] list constructor
   (Felix uses :: like C++ for qualification :(

(c) Felix anonymous functions only accept one argument 
   (needs fixing)

(d) Felix function parameters aren't general patterns: at best
  a single top level tuple match is allowed (ugly constraint)

However the worst problem isn't shown by the correct code:
whilst Ocaml's error messages are sometimes confusing as 
to reason and location, and Felix is generally better at locating
the source of a problem -- Felix sometimes gives very confusing
explanations -- it took me an hour to finally convince myself
I actually had a type error in my previous code, rather than
a compiler bug.

The fact that an ordinary programmer can write a compiler
for a powerful language in Ocaml really shows just how good
Ocaml is :)

---------------------------------
include "std";
open List;

fun snd(x,y)=>y;
fun fst(x,y)=>x;

fun index[t] (l:list[t]) = {
  typedef il_t = int * list [int * t];
  fun f(il:il_t) (e: t) =>
    match il with
    | ?i,?l => i+1, Cons ((i, e),l)
    endmatch
  ;
  return
    rev (snd (
      fold_left
      f of (il_t)
      (0, Empty[int * t]) 
      l
    ))
  ;
}

var x = Empty[int];
x = Cons(11,x);
x = Cons(22,x);
x = Cons(33,x);
x = Cons(44,x);
x = Cons(55,x);
x = Cons(66,x);

val z = index x;
iter 
  (proc (x:int,y:int)
    {
      print x; print " -> "; print y; endl;
    }
  )
  z
;

------------
[skaller@pelican] ~/links/flx>bin/flx -Ilib --force il
0 -> 66
1 -> 55
2 -> 44
3 -> 33
4 -> 22
5 -> 11


-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners