[Camllist] Are map and iter guaranteed to be called in forwards order?
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:   (:) 
From:  Jon Harrop <jon@j...> 
Subject:  Re: [Camllist] Are map and iter guaranteed to be called in forwards order? 
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 (n1) (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, JeanMarie 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 tailrecursive 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 2tuple 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 2tuple, 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 indexvalue 2tuple 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 mailinglist, of course ;). Cheers, Jon.  To unsubscribe, mail camllistrequest@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/camlbugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners