2

Всем доброго времени суток! Я недавно начала изучать функциональное программирование в haskell. И теперь у меня возник вопрос, как работает свертка функций (fold). Пытаюсь ее осознать, но никак не выходит. Желательно прямо подробное объяснение с примерами. Можно какой-то пример, так сказать, по косточкам разобрать. Читала источники, но отчего-то не доходит до меня написанное. Поэтому надеюсь на вашу помощь!

Fire13nyu
  • 163
  • 2
    Совсем грубо: свертка принимает бинарную функцию (например, +) и список (скажем, [1,2,3]) и "просовывает" функцию между элементами списка. Получается 1+2+3. Осознав это, можно начать разбираться между левыми и правыми фолдами, фолдами с штришками и без, фолдами с 1 и без. – arrowd Jun 17 '21 at 11:01
  • 2
    Если вы уже читали разные объяснения и не дошло, то почему вам кажется, что ещё одно, написанное здесь, дойдёт? Чтобы получить объяснение, которое решает ваши конкретные затруднения, перечислите эти затруднения. Возможно задайте более конкретные вопросы. Иначе непонятно, что именно нужно объяснить. – Fyodor Soikin Jun 17 '21 at 11:24
  • Как вариант - можно еще исходники почитать, может понятнее будет – Юрий Козлов Jun 17 '21 at 11:31
  • 1
    Возможно, мои затруднения как-раз связаны с усложнением примеров. Есть варианты использования foldr с тремя аргументами: функция, начальное значение и, видимо, список. В каких случаях используется 3 аргумента, а в каких 2? И чем отличается левый и правый fold? Я могу ошибаться, но вроде как левый связан с хвостовой рекурсией. Хотя и с пониманием хвостовой рекурсии тоже имеются некоторые проблемы... – Fire13nyu Jun 17 '21 at 11:49
  • 1
    Загляните сюда. Мне кажется, там неплохо показано, чем отличаются foldr и foldl. И много еще чего интересно есть – Юрий Козлов Jun 17 '21 at 11:54
  • Можете тогда еще скинуть материал по хвостовой рекурсии? Свертка, вроде, стала попонятнее. – Fire13nyu Jun 17 '21 at 12:18
  • В телеграмме есть чат для изучающих Хаскел. Там Вам лучше помогут, чем я – Юрий Козлов Jun 17 '21 at 12:41
  • Хочу добавить - fold применим не только к списку – Юрий Козлов Jun 17 '21 at 14:47
  • Хороший вопрос. Я бы сказал, отличный. Разобраться с fold очень важно для работы с функциями в хаскеле. Я бы сказал, fold, если коротко, помогает совершать бинарные операции внутри списка. – Максим Строганов Jun 17 '21 at 12:25

1 Answers1

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
talex
  • 2,321