Функция SML foldl - добавление в список с условием

Question

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

Один из единственных вопросов, с которыми у меня действительно возникают проблемы, - это следующий вопрос с использованием foldl:

Рассмотрим скелет программы: fun addGt k xs = List.foldl (...) ... xs;Заполните два пропущенных фрагмента (представленных точками ...), чтобы addGt k xs была суммой тех элементов в xs, которые больше k.Например, addGt 4 [1, 5, 2, 7, 4, 8] = 5 + 7 + 8 = 20

Я уверен, что это действительно легко, но мне очень тяжелопонимание функций foldl и foldr.

Теперь у меня есть следующее (что может показаться очень неправильным, если вы спросите мой компилятор!):

fun addGt(k,xs) = List.foldl ( fn x => if x > k then op+ else 0) 0 xs;

Я был бы очень признателен за помощьс этим вопросом и, возможно, очень коротким комментарием, который пролил бы свет на функции foldl и foldr!

Большое спасибо.

Answer 1

Решение, о котором я только что подумал, следующее:

fun addGt(k, xs) = List.foldl (fn (x, y) => if x >= 5  then x + y else y) 0 xs;

Но позвольте мне объяснить. Прежде всего, проверьте тип функции List.foldl, это:

('a * 'b -> 'b) -> 'b -> 'a list -> 'b

Итак, List.foldl - это функция curry , которая принимает в качестве первого параметра другую функцию типа ('a * 'b -> 'b). Вы использовали (fn x => if x > k then op+ else 0), который имеет тип int -> int. Вместо этого вы должны предоставить List.foldl функцию, которая принимает кортеж типа int * int и возвращает int, так что-то вроде этого: (fn (x, y) => do stuff). Вот почему ваш код не компилировался, вы передали неверный тип функции в foldl.

Теперь вы можете думать о foldl так:

foldl f b [x_1, x_2, ..., x_(n - 1), x_n] = f(x_n, f(x_(n - 1), ..., f(x2, f(x1, b)) ...)), где f - функция типа ('a * 'b -> 'b), b - что-то типа 'b, а список [x_1, x_2, ..., x_(n - 1), x_n] - 'a list.

И похоже на foldr, вы можете думать так:

foldr f b [x_1, x_2, ..., x_(n - 1), x_n] = f(x_1, f(x_2, ..., f(x_(n - 1), f(x_ n, b))

Answer 2

Если вы позвоните foldl f s ls в списке, ls = [x1, x2, ..., xn], тогда вы получите результат:

f(xn, ... f(x2, f(x1, s)))

То есть начинается с поиска

a1 = f(x1, s)

Тогда

a2 = f(x2, a1)

и т. Д., Пока он не пройдёт через список.

Когда это сделано, он возвращает an.

Вы можете думать о a -значениях как о некоем аккумуляторе , то есть ai является результатом, как если бы список был только [x1, x2, ..., xi] (или, скорее, , первые я элементы списка).

Ваша функция обычно будет иметь вид:

fn (x, a) => ...

Что вам нужно сделать, это подумать: хорошо, если у меня есть следующий элемент в списке, x(i+1), и значение ai, которое является результатом для списка [x1, x2, ..., xi], что мне нужно сделать, чтобы найти значение a(i+1), которое является результатом для списка [x1, x2, ..., xi, x(i+1)].

s можно рассматривать как значение, данное пустому списку.

foldr работает так же, только вы начинаете с конца списка, а не с фронта.