Как работает Foldr? - PullRequest
       26

Как работает Foldr?

56 голосов
/ 18 ноября 2009

Кто-нибудь может объяснить, как работает foldr?

Возьмите эти примеры:

Prelude> foldr (-) 54 [10, 11]
53
Prelude> foldr (\x y -> (x+y)/2) 54 [12, 4, 10, 6]
12.0

Я запутался в этих казнях. Есть предложения?

Ответы [ 9 ]

116 голосов
/ 19 ноября 2009

Самый простой способ понять свёртывание - это переписать список, который вы складываете без сахара.

[1,2,3,4,5] => 1:(2:(3:(4:(5:[]))))

теперь, что делает foldr f x, это то, что он заменяет каждый : на f в инфиксной форме и [] на x и оценивает результат.

Например:

sum [1,2,3] = foldr (+) 0 [1,2,3]

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

так

sum [1,2,3] === 1+(2+(3+0)) = 6
72 голосов
/ 18 ноября 2009

foldr начинается с правого конца списка и объединяет каждую запись в списке со значением аккумулятора, используя функцию, которую вы ему даете.Результатом является итоговое значение аккумулятора после «сворачивания» во всех элементах списка.Его тип:

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

, и из этого вы можете видеть, что элемент списка (типа a) является первым аргументом данной функции, а аккумулятор (типа b) равенвторой.

Для вашего первого примера:

Starting accumulator = 54
11 -   54  = -43
10 - (-43) =  53

        ^  Result from the previous line

 ^ Next list item

Итак, вы получили ответ 53.

Второй пример:

Starting accumulator = 54
(6  + 54) / 2 = 30
(10 + 30) / 2 = 20
(4  + 20) / 2 = 12
(12 + 12) / 2 = 12

Таким образом, результат равен 12.

Редактировать: я хотел добавить, это для конечных списков.foldr может также работать с бесконечными списками, но лучше сначала разобраться с конечным случаем, я думаю.

37 голосов
/ 10 августа 2012

Помогает понять разницу между foldr и foldl. Почему foldr называется "сложить справа"?

Первоначально я думал, что это потому, что он потребляет элементы справа налево. И все же foldr и foldl используют список слева направо.

  • foldl оценивает слева направо (ассоциативно слева)
  • foldr оценивает справа налево (ассоциативно справа)

Мы можем прояснить это различие на примере, в котором используется оператор, для которого важна ассоциативность. Мы могли бы использовать человеческий пример, такой как оператор, «ест»:

foodChain = (human : (shark : (fish : (algae : []))))

foldl step [] foodChain
  where step eater food = eater `eats` food  -- note that "eater" is the accumulator and "food" is the element

foldl `eats` [] (human : (shark : (fish : (algae : []))))
  == foldl eats (human `eats` shark)                              (fish : (algae : []))
  == foldl eats ((human `eats` shark) `eats` fish)                (algae : [])
  == foldl eats (((human `eats` shark) `eats` fish) `eats` algae) []
  ==            (((human `eats` shark) `eats` fish) `eats` algae)

Семантика этого foldl такова: человек ест акулу, а затем тот же человек, который ел акулу, затем ест рыбу и т. Д. Пожиратель является аккумулятором.

Сравните это с:

foldr step [] foodChain
    where step food eater = eater `eats` food.   -- note that "eater" is the element and "food" is the accumulator

foldr `eats` [] (human : (shark : (fish : (algae : []))))
  == foldr eats (human `eats` shark)                              (fish : (algae : []))))
  == foldr eats (human `eats` (shark `eats` (fish))               (algae : [])
  == foldr eats (human `eats` (shark `eats` (fish `eats` algae))) []
  ==            (human `eats` (shark `eats` (fish `eats` algae) 

Семантика этого foldr такова: человек ест акулу, которая уже съела рыбу, которая уже съела некоторые водоросли. Питание аккумулятор.

Оба foldl и foldr "отклеивают" едоков слева направо, так что это не причина, по которой мы называем фолдл "левым сгибом". Вместо этого порядок оценки имеет значение.

20 голосов
/ 18 ноября 2009

Подумайте о foldr очень определении :

 -- if the list is empty, the result is the initial value z
 foldr f z []     = z                  
 -- if not, apply f to the first element and the result of folding the rest 
 foldr f z (x:xs) = f x (foldr f z xs)

Так, например, foldr (-) 54 [10,11] должно равняться (-) 10 (foldr (-) 54 [11]), т.е. снова расширяться, равным (-) 10 ((-) 11 54) Таким образом, внутренняя операция 11 - 54, то есть -43; и внешняя операция - 10 - (-43), то есть 10 + 43, следовательно, 53, как вы наблюдаете. Выполните аналогичные шаги для второго случая, и вы снова увидите, как получается результат!

13 голосов
/ 18 ноября 2009

foldr означает сгиб справа, поэтому foldr (-) 0 [1, 2, 3] дает (1 - (2 - (3 - 0))). Для сравнения foldl производит (((0 - 1) - 2) - 3).

Когда операторы не коммутативны foldl и foldr получат разные результаты.

В вашем случае первый пример расширяется до (10 - (11 - 54)), что дает 53.

6 голосов
/ 20 ноября 2009

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

10 - (11 - 54)

от

10 : (11 : [])

Хороший совет, который я получил от Haskell Wikibook, может пригодиться здесь:

Как правило, вы должны использовать foldr в списках, которые могут быть бесконечными или где складка строит структуру данных, и foldl', если список известен как конечный и сводится к одному значению. foldl (без галочки) вообще редко следует использовать.

5 голосов
/ 18 ноября 2009

Я всегда считал http://foldr.com забавной иллюстрацией. См. Лямбда-предельная запись.

2 голосов
/ 30 мая 2017

Я думаю, что простая реализация map, foldl и foldr помогает объяснить, как они работают. Работающие примеры также помогают в нашем понимании.

  myMap f [] = []
  myMap f (x:xs) = f x : myMap f xs

  myFoldL f i [] = i
  myFoldL f i (x:xs) = myFoldL f (f i x) xs

  > tail [1,2,3,4] ==> [2,3,4]
  > last [1,2,3,4] ==> 4
  > head [1,2,3,4] ==> 1
  > init [1,2,3,4] ==> [1,2,3]

  -- where f is a function,
  --  acc is an accumulator which is given initially
  --  l is a list.
  --
  myFoldR' f acc [] = acc
  myFoldR' f acc l = myFoldR' f (f acc (last l)) (init l)

  myFoldR f z []     = z
  myFoldR f z (x:xs) = f x (myFoldR f z xs)

  > map (\x -> x/2) [12,4,10,6] ==> [6.0,2.0,5.0,3.0]
  > myMap (\x -> x/2) [12,4,10,6] ==> [6.0,2.0,5.0,3.0]

  > foldl (\x y -> (x+y)/2) 54 [12, 4, 10, 6] ==> 10.125
  > myFoldL (\x y -> (x+y)/2) 54 [12, 4, 10, 6] ==> 10.125

    foldl from above: Starting accumulator = 54
      (12  + 54) / 2 = 33
      (4 + 33) / 2 = 18.5
      (10  + 18.5) / 2 = 14.25
      (6 + 14.25) / 2 = 10.125`

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

 > foldl (++) "5" ["1", "2", "3", "4"] ==> “51234"

 > foldr (\x y -> (x+y)/2) 54 [12,4,10,6] ==> 12
 > myFoldR' (\x y -> (x+y)/2) 54 [12,4,10,6] ==> 12
 > myFoldR (\x y -> (x+y)/2) 54 [12,4,10,6] ==> 12

    foldr from above: Starting accumulator = 54
        (6  + 54) / 2 = 30
        (10 + 30) / 2 = 20
        (4  + 20) / 2 = 12
        (12 + 12) / 2 = 12
1 голос
/ 06 апреля 2013

Хорошо, давайте посмотрим на аргументы:

  • функция (которая принимает элемент списка и значение (возможный частичный результат) того же типа, что и возвращаемое значение);
  • спецификация начального результата для особого случая пустого списка
  • список;

возвращаемое значение:

  • какой-то окончательный результат

Сначала применяется функция к последнему элементу списка и результату пустого списка. Затем он повторно применяет функцию с этим результатом и предыдущим элементом и т. Д., Пока не получит некоторый текущий результат и первый элемент списка для возврата окончательного результата.

Fold "сворачивает" список вокруг начального результата, используя функцию, которая берет элемент, и некоторый предыдущий результат свертывания. Это повторяет это для каждого элемента. Итак, foldr делает это, начиная с конца списка или с правой стороны.

folr f emptyresult [1,2,3,4] превращается в f(1, f(2, f(3, f(4, emptyresult) ) ) ) . Теперь просто следуйте скобкам при оценке и все.

Важно отметить, что предоставленная функция f должна обрабатывать свое собственное возвращаемое значение в качестве второго аргумента, который подразумевает, что оба должны иметь одинаковый тип.

Источник: мой пост , где я смотрю на него с точки зрения императивного неспешного JavaScript, если вы думаете, что это может помочь.

...