Cartesian product of two or more lists: Difference between revisions

Content added Content deleted
m (→‎{{header|OCaml}}: remove excess whitespace)
Line 1,895: Line 1,895:
''The double semicolons are necessary only for the toplevel''
''The double semicolons are necessary only for the toplevel''


Naive but more readable version
Naive but more readable version<lang ocaml>let rec product l1 l2 =
<lang ocaml>
let rec product l1 l2 =
match l1, l2 with
match l1, l2 with
| [], _ | _, [] -> []
| [], _ | _, [] -> []
Line 1,910: Line 1,908:
(*- : (int * 'a) list = []*)
(*- : (int * 'a) list = []*)
product [] [1;2];;
product [] [1;2];;
(*- : ('a * int) list = []*)
(*- : ('a * int) list = []*)</lang>
</lang>


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.
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.
<lang ocaml>
<lang ocaml>let product' l1 l2 =
let product' l1 l2 =
let rec aux ~acc l1' l2' =
let rec aux ~acc l1' l2' =
match l1', l2' with
match l1', l2' with
Line 1,933: Line 1,929:
(*- : (int * 'a) list = []*)
(*- : (int * 'a) list = []*)
product' [] [1;2];;
product' [] [1;2];;
(*- : ('a * int) list = []*)
(*- : ('a * int) list = []*)</lang>
</lang>
Implemented using nested folds:
Implemented using nested folds:
<lang ocaml>
<lang ocaml>let cart_prod l1 l2 =
let cart_prod l1 l2 =
List.fold_left (fun acc1 ele1 ->
List.fold_left (fun acc1 ele1 ->
List.fold_left (fun acc2 ele2 -> (ele1,ele2)::acc2) acc1 l2) [] l1 ;;
List.fold_left (fun acc2 ele2 -> (ele1,ele2)::acc2) acc1 l2) [] l1 ;;
Line 1,944: Line 1,938:
(*- : (int * char) list = [(3, 'c'); (3, 'b'); (3, 'a'); (2, 'c'); (2, 'b'); (2, 'a'); (1, 'c'); (1, 'b'); (1, 'a')]*)
(*- : (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] [] ;;
cart_prod [1; 2; 3] [] ;;
(*- : ('a * int) list = [] *)
(*- : ('a * int) list = [] *)</lang>
</lang>


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.
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.
<lang ocaml>
<lang ocaml>let rec product'' l =
let rec product'' l =
(* We need to do the cross product of our current list and all the others
(* We need to do the cross product of our current list and all the others
* so we define a helper function for that *)
* so we define a helper function for that *)
Line 1,994: Line 1,986:
*)
*)
product'' [[1; 2; 3];[];[500; 100]];;
product'' [[1; 2; 3];[];[500; 100]];;
(*- : int list list = []*)
(*- : int list list = []*)</lang>

</lang>


=== Better type ===
=== Better type ===


In the latter example, our function has this signature:
In the latter example, our function has this signature:
⚫
<lang ocaml>val product'' : 'a list list -> 'a list list = <fun></lang>
<lang ocaml>
⚫
val product'' : 'a list list -> 'a list list = <fun>
</lang>
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:
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:
<lang ocaml>
<lang ocaml>type 'a tuple = 'a list
type 'a tuple = 'a list


let rec product'' (l:'a list tuple) =
let rec product'' (l:'a list tuple) =
Line 2,027: Line 2,014:


type 'a tuple = 'a list
type 'a tuple = 'a list
val product'' : 'a list tuple -> 'a tuple list = <fun>
val product'' : 'a list tuple -> 'a tuple list = <fun></lang>
</lang>


=={{header|Perl}}==
=={{header|Perl}}==
Retrieved from "https://rosettacode.org/wiki/Cartesian_product_of_two_or_more_lists"