"ocaml_beginners"::[] Cartesian product

Hello,

I'm trying to translate a Haskell function into OCaml and I am stuck.

This is the Haske function:
> cp :: [[a]] -> [[a]]
>; cp [] = [[]]
> cp (xsss) = [y:ys | y <- xs, ys <- cp xss]

And this is one attempt in Ocaml:
let rec cp matrix = match matrix with
| [] -> [[]]
| (xs:ss) -> let rec loop1 a l1 =
let rec loop2 l2 = match l2 with
| [] -> []
| (y::ys) -> (a::y) :: loop2 (cp xss)
| ...

Am I on the right track here or should I be thinking differently?
I don't want to resort to imperative programming.

Any help will be greatly appreciated.

Anders

Messages in this topic (1) Reply (via web post) | Start a new topic

.

On Tue, 19 Dec 2006, Anders Janmyr wrote:

> Hello,
&gt;
> I'm trying to translate a Haskell function into OCaml and I am stuck.
&gt;
> This is the Haske function:
>> cp :: [[a]] -> [[a]]
>;> cp [] = [[]]
>> cp (xsss) = [y:ys | y <- xs, ys <- cp xss]
>
> And this is one attempt in Ocaml:
&gt; let rec cp matrix = match matrix with
> | [] -> [[]]
> | (xs:ss) -> let rec loop1 a l1 =
> let rec loop2 l2 = match l2 with
> | [] -> []
> | (y::ys) -> (a::y) :: loop2 (cp xss)
> | ...
>
> Am I on the right track here or should I be thinking differently?
> I don't want to resort to imperative programming.

Hi Anders,

I would write something like this:

let rec cp = function
[] -> [[]]
| xs :: xss ->
let cpxss = cp xss in
List.flatten
(List.map
(fun y ->
List.map (fun ys -> y :: ys) cpxss)
xs)

It's definitely not easy to read. In addition, you might want to use
List.fold_right instead of List.flatten and List.map, but it makes things
even less clear.

Another option is to use a syntax extension for list comprehensions, such
as pa_compr written by Olivier Andrieu:
http://oandrieu.nerim.net/ocaml/#pa_compr

Martin

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

Messages in this topic (2) Reply (via web post) | Start a new topic

.