Как сделать дополнение в списке с условием?

У меня есть университетский курс по функциональному программированию, где я использую 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!


functional-programming higher-order-functions fold sml
person Lars Holdgaard    schedule 11.05.2011    source источник

Ответы (2)


arrow_upward
9
arrow_downward

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

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 — это карриванная функция, которая принимает первый параметр другой функции типа ('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))

person insumity    schedule 11.05.2011
comment
Большое спасибо за объяснение и ответ! :-) - person Lars Holdgaard; 11.05.2011
comment
Я полагаю, вы имели в виду if x >= k? - person Alex Reinking; 29.01.2021

arrow_upward
2
arrow_downward

Если вы вызовете 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] (точнее, первых i элементов списка ).

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

fn (x, a) => ...

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

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

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

person Sebastian Paaske Tørholm    schedule 11.05.2011
comment
Большое спасибо за объяснение! :-) - person Lars Holdgaard; 11.05.2011