Произведение из 2 списков в ocaml без императивных функций

Question

ERS,

Я пытаюсь научиться функциональному программированию с помощью таблиц 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>

Answer 2

Использование монад ( монад для функционального программирования) может упростить ваш код.

module ListMonad =
struct
  type 'a t = 'a list
  let return x = [x]                                                        
  let bind l f = List.fold_right (fun x acc -> (f x)@acc) l []
  let zero = []                                                             
  let ( >>= ) l f  = bind l f                                              
end;; 

Во-первых, основной вариант использования:

["A";"B"] >>= fun (x ->
[["C"];["D"]] >>= fun y -> x::y);;

Возвращает продукт из списка 2: [["A";"C"];["A";"D"];["B";"C"];["B";"D"]]

И полный вариант использования (продукт списка списков), мы используем List.fold:

 List.fold_right (fun x acc -> product x acc)
   [["a";"b"];["c";"d";"e"];["f";"g"]]     [[]];;

Будет производить:

[["a"; "c"; "f"]; ["a"; "c"; "g"]; ["a"; "d"; "f"]; ["a"; "d"; "g"];
 ["a"; "e"; "f"]; ["a"; "e"; "g"]; ["b"; "c"; "f"]; ["b"; "c"; "g"];
 ["b"; "d"; "f"]; ["b"; "d"; "g"]; ["b"; "e"; "f"]; ["b"; "e"; "g"]]

`

Answer 3

Представьте себе C для вложенного цикла. Далее, идея состоит в том, чтобы перебрать второй список, начиная с хвоста. Поместите это в другой цикл через первый список, начиная с хвоста. Первый раунд достигнет конца обоих списков, и вы хотите, чтобы это вернуло пустой список. Затем начнется возврат с последнего элемента обоих списков. Элемент, который вы хотите вернуть, является первым заголовком списка, совпадающим со вторым заголовком списка. Это относится к тому же списку, который вы только что создали. Причина, по которой он начинается с хвоста, заключается в том, что списки неизменны, поэтому проще просто добавить новый заголовок перед списком. Ваша функция имеет один параметр с двумя списками. Однако вам нужны не списки, а то, что находится внутри списков, и это идет слева от стрелки, головы и хвоста обоих списков. Теперь запомните, вы просматриваете второй список, просматриваете первый список и объединяете головы в обратном порядке.