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

avatar
Enflamed Chicken
7 апреля 2018 в 22:59
624
3
2

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. Я думаю, что лучше задать вопрос о том, как создать список строк.

Источник
PatJ
8 апреля 2018 в 01:08
0

Вы не должны использовать == для сравнения на равенство, а более простой оператор =. В этом конкретном случае это сработает, но в тот день, когда вы будете использовать его для более сложных данных, вы получите неприятные сюрпризы.

Ответы (3)

avatar
fieryphoenix
9 апреля 2018 в 23:32
0

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

avatar
Pierre G.
8 апреля 2018 в 15:02
1

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

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

`

avatar
Mulan
7 апреля 2018 в 23:54
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>
Mulan
8 апреля 2018 в 00:19
0

Если это читает другой мастер Ocaml, я хотел бы знать, как преобразовать product в функцию, которая выводит список кортежей вместо списка списков.

PatJ
8 апреля 2018 в 01:13
0

Поскольку продукты ожидают список списка в качестве аргумента, а кортежи неизвестной длины не могут быть выражены в системе типов, вы не можете. Если вы возьмете два аргумента в качестве входных данных вместо списка, создание кортежей будет довольно простым.

Mulan
8 апреля 2018 в 02:37
0

@PatJ имеет смысл. Спасибо за комментарий ^^