먼저, 내가 읽고있는 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입니다.
답변
답변
의미가 다르므로 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 (:))유형 오류가 발생합니다.
