[Camllist] New to OCaml: can someone explain how this code can be done better?

Jeremy Fincher
 Eric C. Cooper
[
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:  20010623 (19:39) 
From:  Eric C. Cooper <ecc@c...> 
Subject:  Re: [Camllist] New to OCaml: can someone explain how this code can be done better? 
(* Here is one approach to the problem. I think it is more natural to define permute on lists, and then write permute_string by converting to and from lists of characters. As you'll see, the only imperative code is in this conversion step; the rest is purely functional. A simple recursive definition of permute is the following: The only permutation of an empty list is the empty list. Otherwise, the permutations of [x1;...;xN] are obtained by inserting x1 at all possible positions in each of the permutations of [x2;...;xN]. We can translate this directly into ML: *) (* (distribute e [x1;...;xN]) returns the list [ [e;x1;...;xN]; [x1;e;x2;...;xN]; ...; [x1;...;xN;e] ] *) let rec distribute elt = function  (hd :: tl) as list > (elt :: list) :: (List.map (fun x > hd :: x) (distribute elt tl))  [] > [ [elt] ] (* (permute [x1;...;xN] returns the list of all permutations of [x1;...;xN] *) let rec permute = function  x :: rest > List.flatten (List.map (distribute x) (permute rest))  [] > [ [] ] (* Since we probably don't care about the order of the list of permutations, we can be slightly more efficient by defining a tailrecursive combination of flatten and map: *) (* (flat_rev_map f [x1;...;xN]) returns the list [rev (f xN) @ ... @ rev (f x1)] *) let flat_rev_map f list = let rec loop acc = function  x :: rest > loop (List.rev_append (f x) acc) rest  [] > acc in loop [] list let rec permute = function  x :: rest > flat_rev_map (distribute x) (permute rest)  [] > [ [] ] (* Finally, we convert to and from strings using implode and explode functions: *) let explode string = let rec loop i acc = if i = 0 then acc else let i' = i1 in loop i' (string.[i'] :: acc) in loop (String.length string) [] let implode list = let string = String.create (List.length list) in let rec loop i = function  x :: rest > string.[i] < x; loop (i+1) rest  [] > () in loop 0 list; string let permute_string s = List.map implode (permute (explode s)) (* Eric Cooper, ecc@cmu.edu *)  Bug reports: http://caml.inria.fr/bin/camlbugs FAQ: http://caml.inria.fr/FAQ/ To unsubscribe, mail camllistrequest@inria.fr Archives: http://caml.inria.fr