Cartesian product of two or more lists: Difference between revisions

''The double semicolons are necessary only for the toplevel''

 

match l1, l2 with

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

(*- : (int * 'a) list = []*)

product [] [1;2];;

 

Implementation with a bit more tail-call optimization, inroducing a helper function. The order of the result is changed but it should not be an issue for most uses.

let rec aux ~acc l1' l2' =

match l1', l2' with

(*- : (int * 'a) list = []*)

product' [] [1;2];;

Implemented using nested folds:

List.fold_left (fun acc1 ele1 ->

List.fold_left (fun acc2 ele2 -> (ele1,ele2)::acc2) acc1 l2) [] l1 ;;

(*- : (int * char) list = [(3, 'c'); (3, 'b'); (3, 'a'); (2, 'c'); (2, 'b'); (2, 'a'); (1, 'c'); (1, 'b'); (1, 'a')]*)

cart_prod [1; 2; 3] [] ;;

 

Extra credit function. Since in OCaml a function can return only one type, and because tuples of different arities are different types, this returns a list of lists rather than a list of tuples.

(* We need to do the cross product of our current list and all the others

* so we define a helper function for that *)

*)

product'' [[1; 2; 3];[];[500; 100]];;

 

=== Better type ===

 

In the latter example, our function has this signature:

This lacks clarity as those two lists are not equivalent since one replaces a tuple. We can get a better signature by creating a tuple type:

 

let rec product'' (l:'a list tuple) =

 

type 'a tuple = 'a list

 

=={{header|Perl}}==