list - OCamlで2つのリストの積を取るには?

Question

私は2つのリストを持っています:

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

次のような出力リスト c が必要です。

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

リストは不変であるため、ocamlでそれを行う方法は? 私はそれに慣れていません。

Answer 1

新しいリストを返します。リストのデカルト積に本当に興味がある場合は、これで十分です。

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")]

代わりにその奇妙なフラット構造が必要な場合は、追加のリスト連結を使用できます。

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

Answer 2

これは末尾再帰操作ではないため、連結を使用したくない場合は、次を使用できます (より効率的なはずです)。

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

デカルト積の場合は、変更するだけです

b::a::y

の中へ

(a,b)::y

Answer 3

私は問題を2つのサブ問題に分けます：

• まず、関数appendeachが値とリストを受け取り、リスト内の各項目の前にその値を追加した結果を返すことを検討してください。

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

• 次に、2つのリストを取り、最初のリストと2番目のリスト全体の各項目に対してappendeachを呼び出す関数製品について考えます。

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