From: "Eric C. Cooper" <ecc@cmu.edu>
To: caml-list@inria.fr
Subject: Re: [Caml-list] New to OCaml: can someone explain how this code can be done better?
Date: Sat, 23 Jun 2001 15:39:19 -0400 [thread overview]
Message-ID: <3B34F067.CD965358@cmu.edu> (raw)
In-Reply-To: <F13liS01qCcWNYgEj4v00003e3d@hotmail.com>
(* 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
next prev parent reply other threads:[~2001-06-23 19:39 UTC|newest]
Thread overview: 5+ messages / expand[flat|nested] mbox.gz Atom feed top
2001-06-23 5:27 Jeremy Fincher
2001-06-23 19:39 ` Eric C. Cooper [this message]
2001-06-25 18:40 ` Stefano Zacchiroli
2001-06-24 5:49 Jeremy Fincher
2001-06-24 6:03 Jeremy Fincher
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=3B34F067.CD965358@cmu.edu \
--to=ecc@cmu.edu \
--cc=caml-list@inria.fr \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).