recursion/iterator question

recursion/iterator question

[Tato Thetza]

Hi caml-list
Given a list, I would like to iterate over all triplets in the list. For
example, in mathematcs, its not uncommon to have expressions such as
"for all i,j,k in set X, do f(i,j,k)"

The only way I can think of is to create a list with all triplets of the
list, so:
  triplets([1,2,3,4]) = [(1,2,3),(1,2,4),(1,3,4),(2,3,4)]
and take this list and map a function f to it.

questions: 
1) what would be the best way to write triplets?
2) is there a cleaner way to iterate over all triplets in a list?

please excuse my english
Tato T.

Re: [Caml-list] recursion/iterator question

[David Powers]

The best way would probably be to write a permutation function that 
returns a list of triplets given a list, and then to use List.iter and a 
local function to split out each triplet to work on the component 
parts... something like:

let for_each_trip lst =
    let real_work (a, b, c) =
        (* do some stuff with a b and c in here *)
    in
        List.iter real_work (permute_triples lst)

(loose code - forgive my laziness)

This could be made more general by improving the permute code to take a 
number option and to return triplets of that number  (permute 3 lst).  
In addition you could make the internal function (real_work) be a 
parameter of the for_each... which would reduce all of this to the more 
general

List.iter any_function_I_want (permute 3 lst)

Finally, you might want to consider using lazy evaluation in your 
permute function to avoid calculating every permutation up front.  See 
http://caml.inria.fr/pub/docs/manual-ocaml/libref/Lazy.html for more on 
that.

-David

Tato Thetza wrote:
> Hi caml-list
> Given a list, I would like to iterate over all triplets in the list. For
> example, in mathematcs, its not uncommon to have expressions such as
> "for all i,j,k in set X, do f(i,j,k)"
>
> The only way I can think of is to create a list with all triplets of the
> list, so:
>   triplets([1,2,3,4]) = [(1,2,3),(1,2,4),(1,3,4),(2,3,4)]
> and take this list and map a function f to it.
>
> questions: 
> 1) what would be the best way to write triplets?
> 2) is there a cleaner way to iterate over all triplets in a list?
>
> please excuse my english
> Tato T.
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>   

Re: [Caml-list] recursion/iterator question

[Martin Jambon]

On Sun, 16 Apr 2006, Tato Thetza wrote:

> Hi caml-list
> Given a list, I would like to iterate over all triplets in the list. For
> example, in mathematcs, its not uncommon to have expressions such as
> "for all i,j,k in set X, do f(i,j,k)"
>
> The only way I can think of is to create a list with all triplets of the
> list, so:
>  triplets([1,2,3,4]) = [(1,2,3),(1,2,4),(1,3,4),(2,3,4)]
> and take this list and map a function f to it.
>
> questions:
> 1) what would be the best way to write triplets?

You can use list comprehensions.
See http://oandrieu.nerim.net/ocaml/#pa_compr

let triplets l = [+ (x, y, z)
 		 | x <- l
 		 | y <- l
 		 | z <- l
 		 | when x < y && y < z ];;

That's not optimal, but it's pretty clear.


> 2) is there a cleaner way to iterate over all triplets in a list?

You can do that, it should perform better:

let rec iter_full f = function
     [] -> ()
   | x :: l -> f x l; iter_full f l

let iter_tail iter f l = iter_full (fun x l -> iter (f x) l) l

let iter_full3 f l = iter_tail (iter_tail iter_full) f l

let iter3 f l = iter_full3 (fun x y z _ -> f x y z) l



Martin

--
Martin Jambon, PhD
http://martin.jambon.free.fr

Edit http://wikiomics.org, bioinformatics wiki

Re: [Caml-list] recursion/iterator question

[Jon Harrop]

On Sunday 16 April 2006 22:11, Tato Thetza wrote:
> Hi caml-list
> Given a list, I would like to iterate over all triplets in the list. For
> example, in mathematcs, its not uncommon to have expressions such as
> "for all i,j,k in set X, do f(i,j,k)"
>
> The only way I can think of is to create a list with all triplets of the
> list, so:
>   triplets([1,2,3,4]) = [(1,2,3),(1,2,4),(1,3,4),(2,3,4)]
> and take this list and map a function f to it.
>
> questions:
> 1) what would be the best way to write triplets?

As 3-tuples, as you have done.

> 2) is there a cleaner way to iterate over all triplets in a list?

I think you mean _tabulate_ all triplets _from_ a list. You can write a 
function to tabulate all pairs like this:

# let rec f2 = function
    [] -> []
  | a::t -> List.map (fun b -> a, b) t @ f2 t;;
val f2 : 'a list -> ('a * 'a) list = <fun>

and then another to tabulate all triplets like this:

# let rec f3 = function
    [] -> []
  | a::t -> List.map (fun (b, c) -> a, b, c) (f2 t) @ f3 t;;
val f3 : 'a list -> ('a * 'a * 'a) list = <fun>

On the example you gave:

# f3 [1;2;3;4];;
- : (int * int * int) list = [(1, 2, 3); (1, 2, 4); (1, 3, 4); (2, 3, 4)]

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

Re: [Caml-list] recursion/iterator question

[Christian Stork]

On Mon, Apr 17, 2006 at 01:06:22AM +0100, Jon Harrop wrote:
> On Sunday 16 April 2006 22:11, Tato Thetza wrote:
> > Hi caml-list
> > Given a list, I would like to iterate over all triplets in the list. For
> > example, in mathematcs, its not uncommon to have expressions such as
> > "for all i,j,k in set X, do f(i,j,k)"

Just in case you didn't know, you're looking for an enumeration of all
"3-sets" or "combinations" out of the set X.  See for example
http://mathworld.wolfram.com/Combination.html .

> > The only way I can think of is to create a list with all triplets of the
> > list, so:
> >   triplets([1,2,3,4]) = [(1,2,3),(1,2,4),(1,3,4),(2,3,4)]
> > and take this list and map a function f to it.

> > questions:
> > 1) what would be the best way to write triplets?

> As 3-tuples, as you have done.

Or, if you choose to represent triplets as lists of three elements, you can
generalize Jon's solution to


  let rec combs = function
      | (0, _) -> [[]]
      | (n, es) when n > List.length es -> []
      | (n, e::es) -> List.map (fun l -> e::l) (combs (n-1, es)) @ combs (n, es)
  let triplets es = combs (3, es)


Question to the rest of the list:  The ocaml compiler complains with 
  ...
  Warning P: this pattern-matching is not exhaustive.
  Here is an example of a value that is not matched:
  (1, [])
  (However, some guarded clause may match this value.)
  ...

Am I right to assume there's no way to get rid of this warning short of
disabling P-warnings on the command line?  (I can't list all the lacking
patterns since they depend on n, right?)

-- 
Chris Stork   <>  Support eff.org!  <>   http://www.ics.uci.edu/~cstork/
OpenPGP fingerprint:  B08B 602C C806 C492 D069  021E 41F3 8C8D 50F9 CA2F

Re: [Caml-list] recursion/iterator question

[Jon Harrop]

On Monday 17 April 2006 10:36, Christian Stork wrote:
> Or, if you choose to represent triplets as lists of three elements, you can
> generalize Jon's solution to
>
>   let rec combs = function
>
>       | (0, _) -> [[]]
>       | (n, es) when n > List.length es -> []
>       | (n, e::es) -> List.map (fun l -> e::l) (combs (n-1, es)) @ combs
>       | (n, es)
>
>   let triplets es = combs (3, es)
>
> Question to the rest of the list:  The ocaml compiler complains with
>   ...
>   Warning P: this pattern-matching is not exhaustive.
>   Here is an example of a value that is not matched:
>   (1, [])
>   (However, some guarded clause may match this value.)
>   ...
>
> Am I right to assume there's no way to get rid of this warning short of
> disabling P-warnings on the command line?  (I can't list all the lacking
> patterns since they depend on n, right?)

The lacking patterns are covered by (_, []), so you probably want:

  | 0, _ | _, [] -> [[]]

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

Re: [Caml-list] recursion/iterator question

[Jonathan Roewen]

> >   let rec combs = function
> >
> >       | (0, _) -> [[]]
> >       | (n, es) when n > List.length es -> []
> >       | (n, e::es) -> List.map (fun l -> e::l) (combs (n-1, es)) @ combs
> >       | (n, es)
> >
> >   let triplets es = combs (3, es)
> >
> > Question to the rest of the list:  The ocaml compiler complains with
> >   ...
> >   Warning P: this pattern-matching is not exhaustive.
> >   Here is an example of a value that is not matched:
> >   (1, [])
> >   (However, some guarded clause may match this value.)

Personally, if you know it can never be reached, then an assertion is
probably better.

| otherwise -> assert false (* I prefer using a name like otherwise
rather than _ for pure readability value *)

Jonathan

Re: [Caml-list] recursion/iterator question

[Christian Stork]

On Mon, Apr 17, 2006 at 06:07:47PM +0100, Jon Harrop wrote:
> On Monday 17 April 2006 10:36, Christian Stork wrote:
> > Or, if you choose to represent triplets as lists of three elements, you can
> > generalize Jon's solution to

> >   let rec combs = function

> >       | (0, _) -> [[]]
> >       | (n, es) when n > List.length es -> []
> >       | (n, e::es) -> List.map (fun l -> e::l) (combs (n-1, es)) @ combs
> >       | (n, es)

> >   let triplets es = combs (3, es)

> > Question to the rest of the list:  The ocaml compiler complains with
> >   ...
> >   Warning P: this pattern-matching is not exhaustive.
> >   Here is an example of a value that is not matched:
> >   (1, [])
> >   (However, some guarded clause may match this value.)
> >   ...

> > Am I right to assume there's no way to get rid of this warning short of
> > disabling P-warnings on the command line?  (I can't list all the lacking
> > patterns since they depend on n, right?)

> The lacking patterns are covered by (_, []), so you probably want:

>   | 0, _ | _, [] -> [[]]

No, that would generate solutions shorter than the requested n elements.
What we want is something like

    | 1, []
    | 2, [] | 2, [_]
    | 3, [] | 3, [_] | 3, [_;_]
    ...
    | n, [] | n, [_] | n, [_;_] | ... | n, [_;...;_] (* n-1 times '_' *)
    -> []

Anyway, I think it's better not to use pattern matching but to use a
simple if-then-else to circumvent the warning.

-- 
Chris Stork   <>  Support eff.org!  <>   http://www.ics.uci.edu/~cstork/
OpenPGP fingerprint:  B08B 602C C806 C492 D069  021E 41F3 8C8D 50F9 CA2F

Re: [Caml-list] recursion/iterator question

[Christian Stork]

On Tue, Apr 18, 2006 at 01:58:25AM -0700, Christian Stork wrote:
> On Mon, Apr 17, 2006 at 06:07:47PM +0100, Jon Harrop wrote:
> > On Monday 17 April 2006 10:36, Christian Stork wrote:
> > > Or, if you choose to represent triplets as lists of three elements, you can
> > > generalize Jon's solution to

> > >   let rec combs = function

> > >       | (0, _) -> [[]]
> > >       | (n, es) when n > List.length es -> []
> > >       | (n, e::es) -> List.map (fun l -> e::l) (combs (n-1, es)) @ combs
> > >       | (n, es)

> > >   let triplets es = combs (3, es)

> > > Question to the rest of the list:  The ocaml compiler complains with
> > >   ...
> > >   Warning P: this pattern-matching is not exhaustive.
> > >   Here is an example of a value that is not matched:
> > >   (1, [])
> > >   (However, some guarded clause may match this value.)
> > >   ...

> > > Am I right to assume there's no way to get rid of this warning short of
> > > disabling P-warnings on the command line?  (I can't list all the lacking
> > > patterns since they depend on n, right?)

> > The lacking patterns are covered by (_, []), so you probably want:

> >   | 0, _ | _, [] -> [[]]

Oh, I think you meant 
    
    | 0, _  -> [[]]
    | _, [] -> []

and that does indeed work (tho it's less efficient).

-- 
Chris Stork   <>  Support eff.org!  <>   http://www.ics.uci.edu/~cstork/
OpenPGP fingerprint:  B08B 602C C806 C492 D069  021E 41F3 8C8D 50F9 CA2F

Re: [Caml-list] recursion/iterator question

[Damien Doligez]

On 2006-04-17, at 11:36, Christian Stork wrote:

> Question to the rest of the list:  The ocaml compiler complains with
>   ...
>   Warning P: this pattern-matching is not exhaustive.
>   Here is an example of a value that is not matched:
>   (1, [])
>   (However, some guarded clause may match this value.)
>   ...
>
> Am I right to assume there's no way to get rid of this warning  
> short of
> disabling P-warnings on the command line?  (I can't list all the  
> lacking
> patterns since they depend on n, right?)

Since nobody has pointed out the obvious, I'll do it:

You can always disable this warning for a particular pattern-matching
by adding the following as the last clause:

     | _ -> assert false

-- Damien

Re: [Caml-list] recursion/iterator question

[Li-Thiao-Té Sébastien]

Tato Thetza wrote:
> Given a list, I would like to iterate over all triplets in the list. For
> example, in mathematcs, its not uncommon to have expressions such as
> "for all i,j,k in set X, do f(i,j,k)"
> 
> The only way I can think of is to create a list with all triplets of the
> list, so:
>   triplets([1,2,3,4]) = [(1,2,3),(1,2,4),(1,3,4),(2,3,4)]
> and take this list and map a function f to it.
> 
> questions: 
> 1) what would be the best way to write triplets?
> 2) is there a cleaner way to iterate over all triplets in a list?
> 
Hi,

I suggest turning the list into an array, then using for-loops instead 
of trying to explicitly generate the list of all possible triplets. If 
you need to accumulate the results, you can use a list ref. This amounts 
to implementing a set using an array instead of a list; unfortunately it 
is not functional :(

let iterate f l =
   let t = Array.of_list l in
   let n = Array.length t in
   let results = ref [] in
   for i = 0 to n-1 do
     for j = 0 to n-1 do
       for k = 0 to n-1 do
         results := f (t.(i),t.(j),t.(k)) :: results
done done done
;;

-- 
Li-Thiao-Té Sébastien

Re: [Caml-list] recursion/iterator question

[Nils Gesbert]

Li-Thiao-Té Sébastien <sayan@crans.org> a écrit :

» let iterate f l =
»    let t = Array.of_list l in
»    let n = Array.length t in
»    let results = ref [] in
»    for i = 0 to n-1 do
»      for j = 0 to n-1 do
»        for k = 0 to n-1 do
»          results := f (t.(i),t.(j),t.(k)) :: results
» done done done
» ;;

Hi,

A functional version of this could be (assuming f is curryed, and without keeping results) :
let iter3 f l =
   let rec it2 iter g = function
      h::t -> iter (g h) l; it2 iter g t
    | _ -> ()
   in it2 (it2 List.iter) f l

But I think the goal was to iterate over triplets (a,b,c) with a < b < c, not over all triplets. If I am not mistaken, it suffices to replace the l on line 3 by t to get this behaviour.

--
Nils Gesbert

Re: [Caml-list] recursion/iterator question

[Xavier Leroy]

> Given a list, I would like to iterate over all triplets in the list. For
> example, in mathematcs, its not uncommon to have expressions such as
> "for all i,j,k in set X, do f(i,j,k)"
>
> The only way I can think of is to create a list with all triplets of the
> list, so:
>   triplets([1,2,3,4]) = [(1,2,3),(1,2,4),(1,3,4),(2,3,4)]
> and take this list and map a function f to it.

Folds are more general than maps and tend to compose better.
Consider:

let list_fold_right_3 f l1 l2 l3 =
  List.fold_right
    (fun x1 -> List.fold_right (fun x2 -> List.fold_right (f x1 x2) l3) l2)
    l1

Examples:

# list_fold_right_3 (fun x y z a -> (x,y,z)::a) [1;2] [3;4] [5;6] [];;
- : (int * int * int) list =
[(1, 3, 5); (1, 3, 6); (1, 4, 5); (1, 4, 6); (2, 3, 5); (2, 3, 6); (2,
4, 5);
 (2, 4, 6)]
# list_fold_right_3 (fun x y z a -> (x+y+z)::a) [1;2] [3;4] [5;6] [];;
- : int list = [9; 10; 10; 11; 10; 11; 11; 12]
# list_fold_right_3 (fun x y z a -> x*y*z + a) [1;2] [3;4] [5;6] 0;;
- : int = 231

But, yes, if you find yourself doing this often, it's a good idea to
use the syntax extension for list comprehensions.

- Xavier Leroy