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

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

[Jeremy Fincher]

Since I'm learning OCaml, I've been writing little functions as I get a 
grasp on each little bit of the syntax.  One of these functions is 
"permute", which takes a string and returns a list of all the permutations 
of the string.  Here's the function:

let rec permute_rec f s =
  if String.length s = 1 then
    (f ^ s) :: []
  else
    let l = ref [] in
    for i = 0 to ((String.length s) - 1) do
      let c = String.sub s i 1 in
      let rem = (String.sub s 0 i) ^ ((String.sub s (i+1) ((String.length 
s)-i-1))) in
	l := (List.append !l (permute_rec (f^c) rem))
    done;
      !l;;

let permute = permute_rec "";;

Now, I'm sure this isn't the best way to code that function.  What I'm 
hoping is that someone can show me a few things about the function: how to 
make it tail recursive; a better (less imperative?) method of writing it, 
and which parts are not consistent with common/standard OCaml idiom.  
*Anything* I'm shown should at least help me learn, so if you have any 
comments/opinions, please tell me!

Thanks,
Jeremy
_________________________________________________________________
Get your FREE download of MSN Explorer at http://explorer.msn.com

-------------------
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

Re: [Caml-list] New to OCaml: can someone explain how this code can be done better?

[Eric C. Cooper]

(* 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

Re: [Caml-list] New to OCaml: can someone explain how this code can be done better?

[Stefano Zacchiroli]

On Sat, Jun 23, 2001 at 03:39:19PM -0400, Eric C. Cooper wrote:
>    characters.  As you'll see, the only imperative code is in this
>    conversion step; the rest is purely functional.
:-((

let rec explode_string = function
   "" -> []
 | s -> (String.get s 0) :: explode_string (String.sub s 1 (String.length s - 1))
;;
let rec implode_string = function
   [] -> ""
 | h::t -> (String.make 1 h) ^ implode_string t
;;

Sorry, I can't resist :-)

Cheers.

-- 
Stefano "Zack" Zacchiroli <zack@cs.unibo.it> ICQ# 33538863
Home Page: http://www.students.cs.unibo.it/~zacchiro
Undergraduate student of Computer Science @ University of Bologna, Italy
	                - Information wants to be Open -
-------------------
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

Re: [Caml-list] New to OCaml: can someone explain how this code can be done better?

[Jeremy Fincher]

>The function permute_rec is an implementation detail.
>So you scope it _inside_ the permute function

I was worried this would incur a slow down (in Python, nested function 
objects are instantiated when a function is called and destroyed when it 
exits; the code object isn't destroyed, but there still is the additional 
overhead of creating a function object from it.)  I assume now, since it's a 
feature so widely used (I see it anytime I look at others' OCaml code) that 
it doesn't.  Thanks for pointing that out.

Jeremy


_________________________________________________________________
Get your FREE download of MSN Explorer at http://explorer.msn.com

-------------------
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

Re: [Caml-list] New to OCaml: can someone explain how this code can be done better?

[Jeremy Fincher]

Thanks!  Going through and understanding your code helped me a lot, and was 
a terrific aid in seeing the functional (rather than imperative) way of 
looping.  One question, though:

>     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) []

Could this be rewritten as this, to remove the if/else? --

let explode string =
  let rec loop acc = function
    | 0 -> acc
    | i -> loop (string.[i-1] :: acc) (i-1)
  in
  loop [] (String.length string)


Thanks for your excellent examples.

Jeremy
>
>     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 *)
_________________________________________________________________
Get your FREE download of MSN Explorer at http://explorer.msn.com

-------------------
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