폴더 대 폴더 (또는 폴더 ')의 의미

폴더 대 폴더 (또는 폴더 ')의 의미

---

먼저, 내가 읽고있는 Real World Haskell 은 결코 사용하지 foldl않고 대신 사용 한다고 말합니다 foldl'. 그래서 나는 그것을 믿습니다.

하지만 사용하는 경우에 흐릿 해요 foldr대 foldl'. 나는 그들이 다르게 작동하는 방식의 구조를 볼 수 있지만 "어느 쪽이 더 낫다"는 것을 이해하기에는 너무 바보입니다. 둘 다 동일한 대답을 생성하기 때문에 어떤 것이 사용되는지는 중요하지 않은 것처럼 보입니다. 사실,이 구성에 대한 나의 이전 경험은 Ruby 's inject와 Clojure 's reduce에서 왔으며, "왼쪽"과 "오른쪽"버전이없는 것 같습니다. (질문 : 어떤 버전을 사용합니까?)

나 같은 똑똑한 도전에 도움이 될만한 통찰력은 대단히 감사하겠습니다!

---

다음과 같은 foldr f x ys곳 의 재귀ys = [y1,y2,...,yk]

f y1 (f y2 (... (f yk x) ...))

반면 재귀는 foldl f x ys다음과 같습니다.

f (... (f (f x y1) y2) ...) yk

여기서 중요한 차이점은 결과 경우이다 f x y의 값을 사용하여 계산 될 수는 x다음 foldr하지 않습니다 '필요가 전체 목록을 검토 할 수 있습니다. 예를 들어

foldr (&&) False (repeat False)

반환 False반면,

foldl (&&) False (repeat False)

종료되지 않습니다. (참고 : repeat False모든 요소가 무한대의 목록을 만듭니다 False.)

반면에 foldl'꼬리는 재귀적이고 엄격합니다. 무엇이든 (예를 들어, 목록의 숫자를 합하여) 전체 목록을 순회해야한다는 것을 알고 있다면 foldl'공간보다 (아마도 시간이) 효율적 foldr입니다.

---

foldr 다음과 같이 보입니다 :

foldl 다음과 같이 보입니다 :

맥락 : 하스켈 위키에 접어 라

---

의미가 다르므로 foldl와를 교환 할 수 없습니다 foldr. 하나는 왼쪽에서 요소를 접고 다른 하나는 오른쪽에서 접습니다. 이렇게하면 연산자가 다른 순서로 적용됩니다. 이것은 빼기와 같은 모든 비 연관 연산에 중요합니다.

Haskell.org 에는 이 주제에 관한 흥미로운 기사 가 있습니다.

---

요약하자면 foldr누산기 함수가 두 번째 인수에서 게으 르면 더 좋습니다. Haskell Wiki의 Stack Overflow (pun 예정) 에서 더 많은 것을 읽으십시오 .

---

모든 사용의 99 % foldl'가 선호 되는 이유 는 foldl대부분의 사용을 위해 일정한 공간에서 실행될 수 있기 때문입니다.

기능을 수행하십시오 sum = foldl['] (+) 0. 때 foldl'사용되며, 합계는 바로 이렇게 적용, 계산 sum이 같은 것을 사용하는 경우 무한 목록은 (일정한 공간에서 가장 가능성이 영원히 실행 한 것 Int들, Double이야, Float이야. Integers는 경우 일정한 공간보다 더 많은 사용합니다 숫자가)보다 커집니다 maxBound :: Int.

을 사용하면 foldl응답을 저장하는 대신 나중에 평가할 수있는 응답을 얻는 방법의 레시피와 같은 썽크가 구성됩니다. 이 썽 크는 많은 공간을 차지할 수 있으며,이 경우 썽크를 저장하는 것보다 스택을 오버플로하는 것보다 식을 평가하는 것이 훨씬 좋습니다 (스택 오버플로로 이어지고…

희망이 도움이됩니다.

---

그건 그렇고, Ruby inject와 Clojure reduce는 foldl(또는 foldl1사용하는 버전에 따라)입니다. 일반적으로 언어에 하나의 양식 만있는 경우 Python reduce, Perl List::Util::reduce, C ++ accumulate, C # Aggregate, Smalltalk inject:into:, PHP array_reduce, Mathematica Fold등을 reduce포함한 왼쪽 접힘입니다 . 일반적인 Lisp의 기본값은 왼쪽 접힘이지만 오른쪽 접는 옵션이 있습니다.

---

으로 콘라드는 지적, 그 의미는 다르다. 그들은 같은 유형조차 가지고 있지 않습니다.

ghci> :t foldr
foldr :: (a -> b -> b) -> b -> [a] -> b
ghci> :t foldl
foldl :: (a -> b -> a) -> a -> [b] -> a
ghci> 

예를 들어,리스트 추가 연산자 (++)는 다음과 foldr같이 구현할 수 있습니다.

(++) = flip (foldr (:))

동안

(++) = flip (foldl (:))

유형 오류가 발생합니다.

참고 URL : https://stackoverflow.com/questions/384797/implications-of-foldr-vs-foldl-or-foldl