Haskell, Foldr и foldl

Я уже довольно давно пытаюсь обернуть голову в сторону foldr и foldl, и я решил, что следующий вопрос должен решить эту проблему за меня. Предположим, вы передаете следующий список [1,2,3] следующим четырем функциям:

a = foldl (\xs y -> 10*xs -y) 0
b = foldl (\xs y -> y - 10 * xs) 0
c = foldr (\y xs -> y - 10 * xs) 0
d = foldr (\y xs -> 10 * xs -y) 0

Результаты будут -123, 83, 281 и -321 соответственно.

Почему это так? Я знаю, что когда вы передаете [1,2,3,4] в функцию, определенную как

f = foldl (xs x -> xs ++ [f x]) []

он расширяется до ((([] ++ [1]) ++ [2]) ++ [3]) ++ [4]

В том же духе, до чего расширяются приведенные выше функции a, b, c и d?


fold haskell
person Ben Shumway    schedule 12.11.2014    source источник
comment
Вы искали в SO другие вопросы, связанные с foldr / foldl? Многие из них показывают расширения и имеют действительно хорошие объяснения. Вы также можете попробовать выполнить подстановку самостоятельно, заменив рекурсивные вызовы сворачивания их определениями, чтобы получить хорошее представление о том, что происходит.   -  person jberryman    schedule 12.11.2014
comment
Я действительно искал ТАК объяснения, но я все еще не мог их понять. Ни одному из них не удалось показать мне, как заменить вызовы foldl и foldr в выражения, подобные приведенному выше. Я не уверен, как делать замены сам, поэтому задаю этот вопрос. Или, возможно, вы имеете в виду, что я смотрю на то, как foldr и foldl определяются рекурсивно, и прохожу через них с помощью a, b, c и d соответственно. Похоже на хлопот, когда я искал ярлык, но я думаю, если нет другого пути ...   -  person Ben Shumway    schedule 12.11.2014
comment
Я обязательно прокомментирую ответы, когда разберусь   -  person Ben Shumway    schedule 12.11.2014
comment
Вы видели foldl.com и foldr.com?   -  person John L    schedule 12.11.2014
comment
Нет, проверю :)   -  person Ben Shumway    schedule 12.11.2014

Ответы (3)


arrow_upward
2
arrow_downward

Я думаю, что два изображения на странице сгиба Haskell Wiki прекрасно это объясняют.

Поскольку ваши операции не коммутативны, результаты foldr и foldl не будут одинаковыми, тогда как в коммутативной операции они будут:

Prelude> foldl1 (*) [1..3]
6
Prelude> foldr1 (*) [1..3]
6

Использование scanl и scanr для получения списка, включающего промежуточные результаты, - хороший способ увидеть, что происходит:

Prelude> scanl1 (*) [1..3]
[1,2,6]
Prelude> scanr1 (*) [1..3]
[6,6,3]

Итак, в первом случае у нас есть (((1 * 1) * 2) * 3), тогда как во втором случае это (1 * (2 * (1 * 3))).

person Michael Kohl    schedule 12.11.2014

arrow_upward
1
arrow_downward

foldr - это действительно простая идея функции: получить функцию, которая объединяет два аргумента, получить начальную точку, список и таким образом вычислить результат вызова функции из списка.

Вот небольшой совет о том, как представить, что происходит во время foldr вызова:

foldr (+) 0 [1,2,3,4,5]
=> 1 + (2 + (3 + (4 + (5 + 0))))

Все мы знаем, что [1,2,3,4,5] = 1:2:3:4:5:[]. Все, что вам нужно сделать, это заменить [] начальной точкой и : любой функцией, которую мы используем. Конечно, мы можем таким же образом восстановить список:

foldr (:) [] [1,2,3]
=> 1 : (2 : (3 : []))

Мы можем лучше понять, что происходит внутри функции, если посмотрим на подпись:

foldr :: (a -> b -> b) -> b -> [a] -> b

Мы видим, что функция сначала получает элемент из списка, затем аккумулятор и возвращает следующий аккумулятор. Таким образом, мы можем написать нашу собственную foldr функцию:

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f a []     = a
foldr f a (x:xs) = f x (foldr f a xs)

И вот ты где; вы должны иметь лучшее представление о том, как foldr работает, чтобы вы могли применить это к своим проблемам, указанным выше.

person AJF    schedule 12.01.2015

arrow_upward
0
arrow_downward

Функции fold* можно рассматривать как цикл по переданному списку, начиная либо с конца списка (foldr), либо с начала списка (foldl). Для каждого из найденных элементов он передает этот элемент и текущее значение аккумулятора в то, что вы написали как лямбда-функцию. Все, что возвращает эта функция, используется в качестве значения аккумулятора в следующей итерации.

Немного изменив обозначение (acc вместо xs), чтобы показать более ясное значение для первого левого сгиба

a = foldl (\acc y -> 10*acc - y) 0              [1, 2, 3]
  = foldl (\acc y -> 10*acc - y) (0*1 - 1)      [2, 3]
  = foldl (\acc y -> 10*acc - y) -1             [2, 3]
  = foldl (\acc y -> 10*acc - y) (10*(-1) - 2)  [3]
  = foldl (\acc y -> 10*acc - y) (-12)          [3]
  = foldl (\acc y -> 10*acc - y) (10*(-12) - 3) []
  = foldl (\acc y -> 10*acc - y) (-123)         []
  = (-123)

И для вашего первого правого сгиба (обратите внимание, что аккумулятор занимает другое положение в аргументах лямбда-функции)

c = foldr (\y acc -> y - 10*acc) 0              [1, 2, 3]
  = foldr (\y acc -> y - 10*acc) (3 - 10*0)     [1, 2]
  = foldr (\y acc -> y - 10*acc) 3              [1, 2]
  = foldr (\y acc -> y - 10*acc) (2 - 10*3)     [1]
  = foldr (\y acc -> y - 10*acc) (-28)          [1]
  = foldr (\y acc -> y - 10*acc) (1 - 10*(-28)) []
  = foldr (\y acc -> y - 10*acc) 281            []
  = 281
person Michal Charemza    schedule 12.11.2014