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

Question

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

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

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

Я запутался об этих казнях. Какие-либо предложения?

Answer 1

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

Answer 2

foldr средство складывается с правой стороны, поэтому foldr (-) 0 [1, 2, 3] производит (1 - (2 - (3 - 0))). В сравнении foldl производит (((0 - 1) - 2) - 3).

Когда операторы не являются commutativefoldl и foldr получат разные результаты.

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

Answer 3

Подумайте о foldr «s очень definition:

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

Answer 4

Я всегда думал http://foldr.com, чтобы быть забавной иллюстрацией. См. Сообщение Lambda the Ultimate.

Answer 5

Самый простой способ понять 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 

Answer 6

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

10 - (11 - 54)

от:

10 : (11 : [])

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

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

Answer 7

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

Answer 8

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

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

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

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

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

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

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

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

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

Answer 9

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