This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

[Caml-list] New to OCaml: can someone explain how this code can be done better?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2001-06-23 (19:39) From: Eric C. Cooper Subject: Re: [Caml-list] 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
tail-recursive 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' = i-1 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/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

```