Geek asks and answers

How to get a product from two lists in OCaml?

I have two lists:

let a = ["a";"b"];
let b = ["c";"d"];

I need c output list, for example:

c = ["a";"c";"a";"d";"b";"c";"b";"d"];

How to do this in ocaml since lists are immutable? I am new to this.

+5
source share
3 answers

You will return a new list. If you are really interested in the Cartesian product of lists, then this should be enough:

let cartesian l l' = 
  List.concat (List.map (fun e -> List.map (fun e' -> (e,e')) l') l)

# cartesian ["a";"b"] ["c";"d"];;
- : (string * string) list = [("a", "c"); ("a", "d"); ("b", "c"); ("b", "d")]

If you need this weird flat structure, you can use extra list concatenation.

let flat_cartesian l l' = 
  List.concat (List.concat (
    List.map (fun e -> List.map (fun e' -> [e;e']) l') l))
+12
source

If you do not want to use concatenation because it is not a tail recursive operation, you can use the following (which should be more efficient):

let product l1 l2 =
  List.rev (
   List.fold_left
    (fun x a ->
      List.fold_left
       (fun y b ->
         b::a::y
       )
       x
       l2
   )
   []
   l1
 )
;;

For a Cartesian product, just change

b::a::y

at

(a,b)::y
+3
source

:

  • appendeach

    let rec appendeach x lst = match lst with [] -> [] 
                                        | hd::tl -> x::hd::(appendeach x tl);;

  • Then we consider a product of a function with two lists and calls appendeach for each element in the first list and the entire second list

    let rec product lst1 lst2 = match lst1 with [] -> [] | 
                                         hd::tl -> (appendeach hd lst2)@(product tl lst2);;
+1
source

More articles:


All Articles