Всем доброго времени суток! Я недавно начала изучать функциональное программирование в haskell. И теперь у меня возник вопрос, как работает свертка функций (fold). Пытаюсь ее осознать, но никак не выходит. Желательно прямо подробное объяснение с примерами. Можно какой-то пример, так сказать, по косточкам разобрать. Читала источники, но отчего-то не доходит до меня написанное. Поэтому надеюсь на вашу помощь!
1 ответ
Базовая функция foldl :: (a -> b -> a) -> a -> [b] -> a
имеет три аргумента.
- Начальное значение
- функция свертки с типом
a -> b -> a
- список
Возьмем пример foldl plus 0 [1, 2, 3]
, где plus a b = a + b
.
Результатом будет 0 + 1 + 2 + 3
.
Возможно помогут скобки ((0 + 1) + 2) + 3
.
Возможно будет понятнее если показать реализацию этого метода
foldl f a [] = a -- для пустого списка результат равен начальному значению
foldl f a x:xs = foldl f new_a xs -- для не пустого мы вызываем ту же функцию
-- с новым начальным значением и передаем только
-- хвост списка
where new_a = f a x -- новое начальное значение мы получаем путем
-- комбинации старого с первым элементом списка
Версии метода с 1
на конце работают с непустыми спискам беря в качестве начального элемента первый элемент списка
foldl1 f x:xs = foldl f x xs
+
) и список (скажем,[1,2,3]
) и "просовывает" функцию между элементами списка. Получается1+2+3
. Осознав это, можно начать разбираться между левыми и правыми фолдами, фолдами с штришками и без, фолдами с 1 и без.