functional-programming - ocaml 中 2 个列表的乘积(不带命令式函数)

Question

呃，

我正在尝试通过 ocaml 和 CYK 表学习函数式编程，因此没有 List.mem 或任何命令式函数。我的目标是形成 2 个细胞的乘积。

这是我目前拥有的:

let stringlister = function(mystring, newlist) ->
List.append newlist mystring;;

let rec append_func = function([listleft;listright], anslist, i, j) ->
if (j == (List.length listright)) then anslist
else begin
     append_func([listleft;listright], anslist, i, j + 1);
     List.append(anslist (stringlister((List.nth listright j), (stringlister( (List.nth listleft i), [])))))

   end;;

let rec prod_func = function([listleft;listright], anslist, i, j) ->
if (i == (List.length listleft)) then anslist
else begin
     prod_func([listleft;listright], anslist, i + 1, j);
     append_func([listleft;listright], anslist, i, j)
   end;;

let product = function[listleft;listright] ->
if (listleft == [] || listright == []) then []
else prod_func([listleft;listright], [], 0, 0);;

预期的输出应该是这样的:

#product[["A";"B"];["D","E","F","G"]];;
-: string list = ["AD"; "AE"; "AF"; "AG"; "BD"; "BE"; "BF"; "BG"]

#product[["A","B"];[]];;
-: string list = []

我的思考过程是创建一系列递归函数，基本上循环遍历列表，将每个字符串与另一个列表中的每个字符串放置在一起。

我认为我的错误在于我如何附加，特别是在append_func中。我认为更好的问题可能是如何创建字符串列表。

Answer 1

我是 Ocaml 新手，所以也许有不同的方法

let rec flat_map f xs =
  match xs with
  | [] -> []
  | x :: xs -> List.append (f x) (flat_map f xs);;
val flat_map : ('a -> 'b list) -> 'a list -> 'b list = <fun>

let product lists =
  let rec loop acc lists =
    match lists with
    | [] -> [[]]
    | first :: [] -> first |> List.map (fun x -> x :: acc)
    | first :: rest -> first |> flat_map (fun x -> loop (x :: acc) rest)
  in
    loop [] lists;;
val product : 'a list list -> 'a list list = <fun>

product [["A"; "B"]; ["D"; "E"; "F"; "G"]]
- : string list list =
[["D"; "A"]; ["E"; "A"]; ["F"; "A"]; ["G"; "A"]; ["D"; "B"]; ["E"; "B"];
 ["F"; "B"]; ["G"; "B"]]

当然，它适用于任意数量的输入列表

product [["1"; "2"; "3"]; ["A"; "B"; "C"; "D"]; ["+"; "-"]];;
- : string list list =
[["+"; "A"; "1"]; ["-"; "A"; "1"]; ["+"; "B"; "1"]; ["-"; "B"; "1"];
 ["+"; "C"; "1"]; ["-"; "C"; "1"]; ["+"; "D"; "1"]; ["-"; "D"; "1"];
 ["+"; "A"; "2"]; ["-"; "A"; "2"]; ["+"; "B"; "2"]; ["-"; "B"; "2"];
 ["+"; "C"; "2"]; ["-"; "C"; "2"]; ["+"; "D"; "2"]; ["-"; "D"; "2"];
 ["+"; "A"; "3"]; ["-"; "A"; "3"]; ["+"; "B"; "3"]; ["-"; "B"; "3"];
 ["+"; "C"; "3"]; ["-"; "C"; "3"]; ["+"; "D"; "3"]; ["-"; "D"; "3"]]

也许他们使用function读起来更好一点

let rec flat_map f = function
  | [] -> []
  | x :: xs -> List.append (f x) (flat_map f xs)

let product lists =
  let rec loop acc = function
    | [] -> [[]]
    | first :: [] -> first |> List.map (fun x -> x :: acc)
    | first :: rest -> first |> flat_map (fun x -> loop (x :: acc) rest)
  in
    loop [] lists

我们也可以从另一个角度来解决这个问题。注意输出顺序的差异

let product lists =
  let rec loop acc = function
    | [] -> acc
    | first :: rest -> loop acc rest |> flat_map (fun c -> List.map (fun x -> x :: c) first)
  in
    loop [[]] lists;;
val product : 'a list list -> 'a list list = <fun>

product [["1"; "2"; "3"]; ["A"; "B"; "C"; "D"]; ["+"; "-"]];;
- : string list list =
[["1"; "A"; "+"]; ["2"; "A"; "+"]; ["3"; "A"; "+"]; ["1"; "B"; "+"];
 ["2"; "B"; "+"]; ["3"; "B"; "+"]; ["1"; "C"; "+"]; ["2"; "C"; "+"];
 ["3"; "C"; "+"]; ["1"; "D"; "+"]; ["2"; "D"; "+"]; ["3"; "D"; "+"];
 ["1"; "A"; "-"]; ["2"; "A"; "-"]; ["3"; "A"; "-"]; ["1"; "B"; "-"];
 ["2"; "B"; "-"]; ["3"; "B"; "-"]; ["1"; "C"; "-"]; ["2"; "C"; "-"];
 ["3"; "C"; "-"]; ["1"; "D"; "-"]; ["2"; "D"; "-"]; ["3"; "D"; "-"]]

---

上面的flat_map为列表中的每个元素调用了昂贵的List.append。下面的变体收集中间结果，然后通过对 List.concat

的一次调用来构建输出

let flat_map f xs =
  let rec loop k = function
    | [] -> k []
    | x :: xs -> xs |> loop (fun r -> k (f x :: r))
  in
    loop List.concat xs;;
val flat_map : ('a -> 'b list) -> 'a list -> 'b list = <fun>