Как работает складной склад?

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

Ответ 2

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

Ответ 3

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

Ответ 4

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

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

Ответ 5

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

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

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

Ответ 6

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

10 - (11 - 54)

от

10 : (11 : [])

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

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

Ответ 7

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

Ответ 8

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

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

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

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

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

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

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

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

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

Ответ 9

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