`foldl`과 `foldr`의 차이

AI 요약

foldl과 foldr는 이름처럼 리스트를 서로 반대 방향으로 훑지 않습니다. 둘 다 리스트의 구조를 왼쪽에서 오른쪽으로 따라가지만, 연산을 묶는 방식이 다릅니다. foldl (⊗) v [e0, e1, ..., en]은 (...((v ⊗ e0) ⊗ e1)...) ⊗ en처럼 왼쪽 결합합니다. 반면 foldr (⊗) v [e0, e1, ..., en]은 e0 ⊗ (e1 ⊗ (... ⊗ (en ⊗ v)))처럼 오른쪽 결합합니다.

엄격한 언어에서의 차이

엄격한 언어에서는 가장 안쪽 표현부터 계산합니다. foldl (+) 0 [1, 2, 3, 4]는 (((0 + 1) + 2) + 3) + 4로 계산하고, foldr는 1 + (2 + (3 + (4 + 0)))로 계산합니다. 덧셈처럼 결합법칙과 교환법칙이 성립하는 연산이라면 결과는 같지만 계산 순서는 다릅니다. foldl은 리스트를 순회하면서 누산값을 갱신하므로 꼬리 재귀로 구현할 수 있습니다. 반면 foldr는 결과를 계산하려면 리스트 끝까지 먼저 도달해야 하므로 길이 n인 리스트에서 n개의 스택 프레임이 필요합니다.

지연 평가와 `foldl'`

Haskell의 지연 평가에서는 foldl (+) 0 [1, 2, 3, 4]가 곧바로 덧셈을 수행하지 않습니다. (((0 + 1) + 2) + 3) + 4에 해당하는 계산을 thunk로 쌓아 두고, 결과가 요구될 때 평가합니다. 입력이 길어지면 누산 과정이 큰 thunk로 남아 선형 공간을 쓸 수 있습니다. 리스트 자체가 스트림처럼 필요한 부분만 메모리에 올리는 상황에서는 이 공간 사용이 특히 부담됩니다.

foldl'은 다음 요소로 넘어가기 전에 누산값을 강제로 평가합니다. 그래서 큰 thunk를 쌓지 않고 리스트를 순회하며 누산값을 갱신합니다. 원문은 누산 함수가 엄격한 경우 foldl'을 권합니다. 예시로 Map.delete를 적용할 때도 함수가 엄격하므로 foldl'을 쓰라고 설명합니다. 다만 리스트가 작다면 성능 차이는 대개 미세 최적화에 그칩니다.

지연 평가에서 `foldr`가 유리한 경우

foldr는 재귀 호출을 결과 표현식의 안쪽에 둡니다. 누산 함수가 두 번째 인자를 즉시 평가하지 않는다면 결과 일부를 먼저 만들고 나머지는 thunk로 남길 수 있습니다. 예를 들어 foldr (:) []는 첫 원소와 나머지 리스트를 연결한 결과를 반환하며, 나머지 부분은 사용될 때까지 평가하지 않습니다. 원소를 두 배로 만드는 함수로 foldr를 쓰고 take 2로 앞부분만 소비하면, 뒤쪽 리스트를 전부 계산하지 않아도 됩니다. 따라서 누산 함수가 두 번째 인자에 느슨하고 결과를 일부만 소비한다면 foldr가 작업량을 줄이고 무한 리스트도 처리할 수 있습니다.

반대로 누산 함수가 엄격하면 리스트 전체를 소비해야 하므로 foldr의 지연성이 이점을 주지 않습니다. 원문은 리스트에서 누산 함수가 엄격할 때 foldl'을, 두 번째 인자에 느슨할 때 점진적 계산을 위해 foldr를 쓰라고 정리합니다. 이 기준에서 일반 foldl은 큰 thunk를 만들고 foldr'도 리스트 처리에 이점이 없어 피하라고 권합니다.

다른 자료구조에서는 달라집니다

이 조언은 일반적인 cons 리스트에 관한 내용입니다. 리스트의 나머지 부분이 오른쪽에 놓이는 구조와 달리, SnocList처럼 뒤에 원소를 붙이는 구조에서는 결합 방향의 이점도 뒤집힙니다. 트리처럼 원소가 양쪽에 놓인 자료구조에서는 foldl과 foldr 중 어느 쪽이 더 낫다고 단정하기 어렵습니다. 성능이 중요하다면 연산 (<>)의 결합 순서를 특정하지 않는 foldMap이나 foldMap'을 고려할 수 있습니다. 다만 글이 작성될 당시 foldMap'은 base-4.13.0.0에 들어갈 예정이었습니다.

Lobsters 반응

• @ryan-duve — 오늘에서야 thunk가 무엇인지 알았습니다. 글은 먼저 foldl과 foldr가 왼쪽과 오른쪽에서 접는 연산이 아니며, 둘 다 리스트를 왼쪽에서 오른쪽으로 순회하고 결합 방식이 다르다고 설명합니다. 그런데 이어지는 설명을 보면 오른쪽의 두 항목을 먼저 처리한 다음 오른쪽에서 왼쪽으로 진행하는 것처럼 보입니다. 지연 평가와 엄격한 구현의 내부 동작이 성능에 미치는 영향에 관한 설명이라는 점은 알겠지만, 제가 예상하는 왼쪽·오른쪽 접기와 최종 결과를 구별하기 어렵습니다. 성능에는 나쁠 수 있겠습니다.

원문: Haskell Blog / 번역·요약: Trawling