foldl과 foldr의 근본적인 차이, 정확히 이해하기

핵심 요약

• foldl과 foldr은 '왼쪽에서'와 '오른쪽에서' 접는 것이 아니라, 같은 순서로 리스트를 순회하되 연산의 결합 방식만 다르다.
• foldl은 왼쪽 결합으로 (((v ⨂ e0) ⨂ e1) ⨂ e2)처럼 동작하고, foldr은 오른쪽 결합으로 e0 ⨂ (e1 ⨂ (e2 ⨂ v))처럼 동작한다.
• 순수 언어에서 foldl은 첫 원소부터 축적값을 업데이트하며 상수 공간에서 동작하지만, foldr은 마지막 원소까지 도달해야 하므로 리스트 크기에 비례하는 스택 프레임이 필요하다.
• 게으른 언어(Haskell)에서 foldl은 역설적으로 더 나쁜데, 각 연산이 thunk로 지연되어 리스트 크기에 비례하는 메모리를 사용한다.
• foldl'은 foldl의 strict 버전으로, thunk를 강제하며 다음 원소로 진행하여 상수 공간 동작을 복원한다.
• 게으른 언어에서 foldr은 오른쪽 결합 구조 덕분에 이미 약한 정규형(WHNF)으로 반환될 수 있어 부분 평가와 지연 계산이 가능하다.
• accumulation 함수가 엄격(strict)하면 foldl'을 사용하고, 두 번째 인자에 게으르면(lazy) foldr을 사용해야 한다.
• foldl과 foldr'은 리스트에서 항상 최악이므로 피해야 하며, 다른 자료구조(snoc list, tree 등)에서는 최적 선택이 달라질 수 있다.