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

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

[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

это помогает понять различие между 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 "слезьте" едоков слева направо, так что это не причина, по которой мы называем foldl как "левая складка". Вместо этого имеет значение порядок оценки.

думал о 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 как вы наблюдаете. Пройдите аналогичные шаги для вашего второго случая, и вы снова увидите, как формируется результат!

foldr означает сложить справа, так что foldr (-) 0 [1, 2, 3] производит (1 - (2 - (3 - 0))). В сравнении foldl производит (((0 - 1) - 2) - 3).

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

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

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

10 - (11 - 54)

от:

10 : (11 : [])

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

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

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

Я думаю, что реализация 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

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

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

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

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

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

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

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

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

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