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

[Jon Harrop <jon@jdh30.plus.com>]

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