Как использовать fold для сложной функции в ocaml

Как следует из названия, я хочу использовать fold. Если я правильно понимаю, раньше он применял функцию к каждому элементу в списке. Это то, что я хочу сделать со своей функцией, но я не знаю, как ее отформатировать.

Вот функция, которую я хочу использовать с fold :

let pairing list =
let rec aux counter length paired list = match list with
| [] -> paired
| [head] -> paired
| head :: head' :: tail -> if counter = length then aux (counter-1) length ((head, head) :: paired) (head :: head' :: tail) else aux counter length ((head, head') :: paired) (head' :: tail)
in List.rev(aux (List.length(listheads list)) (List.length(listheads list)) [] (listheads list));;

Что он делает, так это возвращает список всех элементов в списке, соединенных вместе.

Например, если мой список [3;4;2], он должен вернуть

[(3,3); (3,4); (3,2); (4,3); (4,4); (4,2); (2,3); (2,4); (2,2)]

На данный момент она возвращает только [(3,3); (3,4); (3,2)], потому что функция применяется только к первому элементу списка.

Вот все вспомогательные функции:

let rec member list x = match list with
| [] -> false
| head :: tail -> head = x || member tail x

let head_list list =
let rec aux l1 list = match list with
 | [] -> l1
 | (x,y) :: tail -> aux (x :: l1) tail
in List.rev (aux [] list);;

let head'_list list =
let rec aux l2 list = match list with
 | [] -> l2
 | (x,y) :: tail -> aux (y :: l2) tail
in List.rev (aux [] list);;

let listheads list =
let rec aux returnlist l1 l2 = match l1 with
| [] -> returnlist
| head :: tail -> if member l2 head = true && member returnlist head = false then aux (head :: returnlist) tail l2 else aux returnlist tail l2
in List.rev(aux [] (head_list list) (head'_list list));;

Что делает listheads, так это то, что он берет мой первоначальный список (скажем, [(3,4); (4,2); (2,3); (4,7); (9,4)]), использует head_list и head'_list, чтобы определить, какие целые числа находятся в позиции head и head' в кортеже, и помещает их в список (в случае, который я дал, [3;4;2] ).

Я знаю, что fold принимает функцию, пустой список и список в качестве аргументов, но я не знаю, как использовать сопряжение с fold.


tuples fold ocaml
person John Doe    schedule 06.10.2018    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Ваш код должен сделать двойной проход по списку

   let pairing l =
     let second_pass x acc y = ......  in
     let first_pass  acc el = .......  in
     List.fold_left first_pass [] l |> List.rev

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

Вот результат, который у меня есть:

    utop # pairing [3 ; 4 ; 2];;
    - : (int * int) list =
    [(3, 3); (3, 4); (3, 2); (4, 3); (4, 4); (4, 2); (2, 3); (2, 4); (2, 2)]
person Aldrik    schedule 11.10.2018

arrow_upward
0
arrow_downward

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

Возможно, было бы более плодотворно просто отлаживать код. Мне кажется, ты используешь счетчик наоборот. Его начальное значение равно длине списка и уменьшается при каждом рекурсивном вызове. Но ваш тест на завершение проверяет длину списка. Мне кажется, вы должны тестировать против 0 (или, возможно, 1).

Если у вас есть функция f, которая делает что-то интересное со значением, и у вас есть список значений, вы можете использовать List.map для получения списка значений f, применяемых к каждому элементу списка. Сгиб для этого не нужен.

Целью свертки является вычисление чего-то другого, кроме списка значений функции. Например, если каждый вызов f создает список значений, вы можете использовать свертку, чтобы продолжать объединять эти списки в более длинный список.

Допустим, f превращает значение x в список [x; x]. Затем вы можете создать (обратный) двойной список примерно так:

let f x = [x; x]

let double l =
    let aux sofar x = f x @ sofar in
    List.fold_left aux [] l

# double [1;2;3];;
- : int list = [3; 3; 2; 2; 1; 1]

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

person Jeffrey Scofield    schedule 06.10.2018