Во-первых, позвольте мне заметить, что использование Fold для реализации этой операции выглядит несколько вынужденным, поскольку вы должны проходить по обоим спискам одновременно.Однако Fold объединяет элементы единого списка.Тем не менее, здесь есть реализация.
let e [] = []
let f x hxs (y::ys) = (x*y) :: hxs ys
let prodList xs ys = List.fold_right f xs e ys
Выглядит немного сложно, поэтому позвольте мне объяснить.
Универсальное свойство сгиба вправо
Сначала вы должны знать следующее свойство fold_right.
h xs = fold_right f xs e
тогда и только тогда, когда
h [] = e
h (x::xs) = f x (h xs)
Это означает, что если мы запишем умножение списков в рекурсивной форме ниже, то мы можем использовать e и fнаписать это с помощью сгиба, как указано выше.Обратите внимание, что мы работаем с двумя списками, поэтому h принимает два аргумента.
Базовый случай - пустые списки
Умножение двух пустых списков возвращает пустой список.
h [] [] = []
Как записать это в форме выше?Просто абстрагируйтесь по второму аргументу.
h [] = fun [] -> []
Итак,
e = fun [] -> []`
Или, что эквивалентно,
e [] = []
Рекурсивный регистр - непустые списки
h (x::xs) (y::ys) = x*y :: h xs ys
Или, используя только один аргумент,
h (x::xs) = fun -> (y::ys) -> x*y :: h xs ys
Теперь нам нужно переписать это выражение в виде h (x::xs) = f x (h xs).Это может показаться сложным, но нам просто нужно абстрагироваться от x и h xs.
h (x::xs) = (fun x hxs -> fun (y::ys) -> x*y :: hxs ys) x (h xs)
, поэтому мы имеем, что f определяется как
f = fun x hxs -> fun (y::ys) -> x*y :: hxs ys
или, что эквивалентно,
f x hxs (y::ys) = x*y :: hxs ys
Решение в виде сгиба вправо
Определив как e, так и f, мы просто подключаем затем в сгиб согласно первому уравнению свойства выше.И мы получим
h xs = List.fold_right f xs e
или эквивалентно
h xs ys = List.fold_right f xs e ys
Понимание реализации
Обратите внимание, что тип List.fold_right f xs e равен int list -> int list, таким образом, фолд строит функцию по спискам, которая при некотором ys умножит его на заданный параметр xs.
Для пустого xs вы ожидаете пустое ys и вернете пустой результат так,
e [] = fun [] -> []
Что касается рекурсивного случая, то функция f в fold_right должен реализовать решение для x::xs из решения для xs.Поэтому f принимает x типа int и функцию hxs типа int list -> int list, которая реализует умножение для хвоста, и она должна реализовывать умножение для x::xs.
f x hxs = fun (y::ys) -> x*y :: hxs ys
Итак, f создает функцию, которая умножает x на y, а затем применяет к ys уже построенному hxs, который умножает xs на список.