foldr는 어떻게 작동합니까?

foldr는 어떻게 작동합니까?

---

아무도 어떻게 foldr작동 하는지 설명 할 수 있습니까 ?

다음 예를 살펴보세요

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

나는 이러한 처형에 대해 혼란 스럽습니다. 어떤 제안?

---

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무한 목록에서도 작업 할 수 있지만 유한 한 경우를 먼저 살펴 보는 것이 가장 좋습니다.

---

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 오른쪽에서 왼쪽으로 평가 (오른쪽 연관)

연관성이 중요한 연산자를 사용하는 예를 통해 이러한 구분을 명확히 할 수 있습니다. 연산자 "eats"와 같은 인간의 예를 사용할 수 있습니다.

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 : [])

A good piece of advice that I got from the Haskell Wikibook might be of some use here:

As a rule you should use foldr on lists that might be infinite or where the fold is building up a data structure, and foldl' if the list is known to be finite and comes down to a single value. foldl (without the tick) should rarely be used at all.

---

I've always thought http://foldr.com to be a fun illustration. See the Lambda the Ultimate post.

---

I think that implementing map, foldl and foldr in a simple fashion helps explain how they work. Worked examples also aid in our understanding.

  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

---

Ok, lets look at the arguments:

• a function (that takes a list element and a value (a possible partial result) of the same kind of the value it returns);
• a specification of the initial result for the empty list special case
• a list;

return value:

• some final result

It first applies the function to the last element in the list and the empty list result. It then reapplies the function with this result and the previous element, and so forth until it takes some current result and the first element of the list to return the final result.

Fold "folds" a list around an initial result using a function that takes an element and some previous folding result. It repeats this for each element. So, foldr does this starting at the end off the list, or the right side of it.

folr f emptyresult [1,2,3,4] turns into f(1, f(2, f(3, f(4, emptyresult) ) ) ) . Now just follow parenthesis in evaluation and that's it.

One important thing to notice is that the supplied function f must handle its own return value as its second argument which implies both must have the same type.

Source: my post where I look at it from an imperative uncurried javascript perspective if you think it might help.

참고URL : https://stackoverflow.com/questions/1757740/how-does-foldr-work