Foldr는 어떻게 작동합니까?

StackOverflow https://stackoverflow.com/questions/1757740

  •  20-09-2019
  •  | 
  •  

문제

누구든지 어떻게하는지 설명 할 수 있습니다 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 Infix 양식 및 [] ~와 함께 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 IS : 인간은 상어를 먹은 다음 상어를 먹은 동일한 인간이 물고기를 먹습니다. 먹는 사람은 축적기입니다.

이것을 다음과 대조하십시오.

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 IS : 인간은 이미 조류를 먹은 물고기를 이미 먹은 상어를 먹습니다. 음식은 축합기입니다.

둘 다 foldl 그리고 foldr 왼쪽에서 오른쪽으로 "껍질을 벗기"이터를 먹기 때문에 Foldl을 "Left Fold"라고하는 이유는 아닙니다. 대신, 평가 순서가 중요합니다.

생각하십시오 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 재미있는 일러스트레이션이 되십시오. 참조 람다 궁극 게시하다.

간단한 방식으로지도, 폴드 및 폴드를 구현하면 그들이 어떻게 작동하는지 설명하는 데 도움이된다고 생각합니다. 일한 사례는 또한 우리의 이해에 도움이됩니다.

  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

좋아, 논쟁을 보자 :

  • 반환하는 동일한 종류의 값의 목록 요소와 값 (가능한 부분 결과)을 취하는 함수;
  • 빈 목록 특별 케이스에 대한 초기 결과의 사양
  • 목록;

반품 값 :

  • 몇 가지 최종 결과

먼저 목록의 마지막 요소와 빈 목록 결과에 함수를 적용합니다. 그런 다음이 결과와 이전 요소로 기능을 다시 얻습니다. 현재 결과와 목록의 첫 번째 요소가 최종 결과를 반환 할 때까지 앞으로 나옵니다.

요소와 이전 접기 결과를 가져 오는 함수를 사용하여 초기 결과 주변의 목록을 "접는"접히십시오. 각 요소에 대해 이것을 반복합니다. 따라서 Foldr는 목록 또는 오른쪽에서 끝까지 시작합니다.

folr f emptyresult [1,2,3,4] 로 변합니다 f(1, f(2, f(3, f(4, emptyresult) ) ) ) . 이제 평가에서 괄호를 따르십시오.

주목해야 할 중요한 것은 제공된 기능이 f 두 번째 인수는 동일한 유형을 가져야한다는 것을 의미하는 두 번째 인수로 자체 반환 값을 처리해야합니다.

원천: 내 게시물 당신이 도움이 될 수 있다고 생각하면 명령적인 자바 스크립트 관점에서 내가 그것을 보는 곳.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top