요약
foldl과 foldr는 왼쪽·오른쪽부터 접는 함수가 아니라 묶는 방향이 다른 함수입니다.
Haskell 개발자 알렉시스 킹이 2019년 GitHub에 올린 설명을 Haskell 블로그가 다시 실었습니다. 두 함수의 이름 때문에 생기는 오해를 풀고, 리스트에서 어느 쪽을 써야 하는지 정리한 글입니다.
왜 중요한가
- 엄격한 언어에서 익힌 직관이 지연 평가(값이 필요할 때까지 계산을 미루는 방식) 언어인 Haskell에서는 뒤집힌다는 점을 보여 줍니다.
- 리스트를 끝까지 계산하면
foldl', 결과를 조금씩 쓰면foldr를 고르라는 간단한 기준을 줍니다.
핵심 내용
- 두 함수 모두 리스트를 왼쪽에서 오른쪽으로 훑고, 연산을 묶는 방향(결합 방향)만 다릅니다.
- 엄격한 언어에서는
foldl이 꼬리 재귀(마지막 동작이 자기 호출이라 반복문처럼 도는 재귀)로 일정한 메모리만 씁니다. - 같은 상황에서
foldr는 리스트 끝에 닿아야 계산을 시작하므로 리스트 길이만큼 스택을 씁니다. - Haskell의
foldl은 미뤄 둔 계산인 썽크(thunk)를 리스트 길이만큼 쌓아 메모리를 낭비합니다. foldr는 결합 함수가 두 번째 인자를 늦게 평가하면 결과의 앞부분만 꺼내 쓸 수 있어 무한 리스트도 다룹니다.
HN 반응
- 일부 이용자는 같은 방향으로 훑는다는 설명이 Haskell의 단방향 연결 리스트에만 맞고, 배열에서는
foldr가 오른쪽부터 훑는다고 지적했습니다. - 직접 재귀가 더 읽기 쉽지 않으냐는 물음에는 fold에 익숙해지면 의도가 더 빨리 보이고 GHC 최적화에도 유리하다는 답이 이어졌습니다.
리스트에서 foldr이 foldl과 다른 재미있는 점은, 각 접기 단계마다 제어 흐름을 누적 함수에 온전히 넘겨준다는 것입니다. 그래서 foldr로 리스트에 대한 임의의 순회를 구현할 수 있습니다. foldl'은 물론이고 중간에 빠져나오는 순회도 가능합니다. 다음을 참고하세요. https://github.com/quchen/articles/blob/master/useful_techniques.md#bouncy-folds
맞습니다. foldr은 for_와 같기 때문입니다. 컨테이너를 돌면서 각 원소마다 부수 효과가 있는 동작(다른 언어에서는 "뭔가 한다"고 부를 법한 것)을 수행하는 거죠. foldr을 쓴 코드는 언제든 for_를 쓴 코드로 다시 쓸 수 있고, 저는 for_ 쪽이 훨씬 명확하다고 생각합니다!
(이 내용은 제 글 "foldl traverses with State, foldr traverses with anything"에서 설명했습니다. https://h2.jaguarpaw.co.uk/posts/foldl-traverses-state-foldr-traverses-anything/ )
글쎄요,
foldr은 (서로를 정의할 수 있다는 범위 안에서) 리스트에 대한for_(또는traverse)의 구현일 뿐입니다.map이fmap의 구현인 것과 같은 식이죠.traverse의 핵심은 그것을 펑터(functor)가 제공한다는 데 있습니다.함수 이름을 가장 일반적인 것(일관성을 위해)으로 할지 가장 구체적인 것(직관성을 위해)으로 할지는 Prelude의 오랜 골칫거리입니다 :)
다시 말해
foldr(인자 순서를 뒤집은 것)은 리스트를 처치 인코딩(Church encoding)으로 바꿔 줍니다. 생성자만 "갈아 끼우는" 것이라(:는f로,[]는z로) 리스트의 정보를 하나도 잃지 않거든요. 리스트를 재귀로 돌면서 쓸 수 있는 함수라면foldr로도 쓸 수 있습니다.어느 시점부터는 함수를 직접 풀어 쓰는 게 더 쉽지 않나요? 이렇게요.
fold로 억지로 끼워 맞추는 대신에요.
fold를 아직 모른다면 그렇다고 볼 수 있습니다.
이미 안다면, foldl'을 쓰는지 foldr을 쓰는지만 슬쩍 봐도 그 함수가 무엇을 할 수 있는지 알 수 있어서 이해하는 수고가 조금 줄어듭니다.
리스트 순회는 보통 코드가 짧아서 어느 쪽이든 큰 차이는 없습니다.
이런 경우에도 fold를 쓰는 장점이 하나 있습니다. Haskell을 처음 접한 사람들은 패턴 매칭의 위력에 너무 빠져들었다가 (그리고 그 때문에 헷갈려 하다가) 이상하리만치 복잡한 리스트 순회를 손으로 써 내려가곤 합니다. 더 간단한 수단이 있는데도 아직 몸에 익지 않아서요.
Haskell 프로그래머 사이에는 명시적 재귀가 함수형 프로그래밍의 goto라는 관점이 꽤 널리 퍼져 있습니다. 접기나 순회 전용 함수를 쓰면 그 함수가 무엇을 하려는지 더 분명히 드러난다는 거죠. 이 관점의 극단에는 재귀 스킴(recursion schemes)과 "zygohistomorphic prepomorphism" 같은 밈이 있는데, 리스트에는 거의 틀림없이 과하지만 더 큰 재귀 구조를 순회할 때는 쓸모가 있을 수 있습니다. 저는 개인적으로 거의 항상 리스트 원소를 매핑할 모노이드를 찾아서
fold :: (Monoid m, Foldable t) => t m -> m을 쓰는 쪽을 선호합니다. Python에서reduce()대신sum()을 쓰는 것과 본질적으로 같습니다.저는 어떤 문제를 오래 붙들고 고민하다 보면 매번 F-대수(F-Algebra)와 F-쌍대대수(F-CoAlgebra)로 돌아오게 됩니다.
재귀는 대부분 fold와 unfold로 표현됩니다.
'fold'를 비틀고 구겨서 범용 리스트 반복자처럼 쓰는 게 "명확함"을 주지는 않습니다.
그런데 함수형 프로그래밍에는 "범용 리스트 반복자" 같은 건 없습니다. 출력이 무엇인지, 이전 반복의 값을 봐야 하는지 등이 중요하니까요.
링크된 글 중 하나(Fusion에 관한 것)에서 짚고 있듯이, 특히 GHC에는 fold를 위한 최적화와 재작성 규칙이 많습니다. 단순 재귀로 작성된 Prelude 함수 중 상당수도 GHC 최적화기의 여러 단계에 힌트를 주려고 최적화된 fold 표현을 함께 갖고 있습니다.
이런 주제가 대개 그렇듯, 명확성이나 미학과 잠재적인 성능 최적화 사이에 흥미로운 스펙트럼이 있는 것 같습니다. 특히 "학습 곡선을 넘으면 명확성과 미학에 대한 취향이 뒤집히는" 경우가 많아 보이는데, 어느 정도 익숙해지면 명시적으로 쓴 재귀를 따라가며 추론하는 것보다 fold가 더 빨리 읽히기 때문입니다.
fold에 익숙해지고 그런 방식으로 생각하는 데 편해지고 나면, 실제로는 fold로 쓰는 쪽이 더 쉬워진다고 생각합니다.
아니면 명시적 재귀 대신 그냥
for_를 쓰면 되고요...이 설명은 논란의 여지가 있습니다. 단일 연결 리스트(singly-linked list)를 전제로 한다면 모를까요. 단일 연결 리스트는 정의상 왼쪽에서 오른쪽으로만 순회할 수 있으니까요(리스트 길이가 무한할 수도 있는 지연(lazy) 언어에서는 더더욱 그렇습니다). 엄격(strict) 언어에서 배열이나 이중 연결 리스트로 구현하면 foldr의 순회 순서는 오른쪽에서 왼쪽이 됩니다.
더 정확하게 말하면, Haskell에서는 리스트를 왼쪽에서 오른쪽으로만 순회할 수 있고, 그래서 Haskell의 foldl과 foldr 구현은 둘 다 필연적으로 그것을 바탕으로 한다고 해야 합니다.
맞습니다. 이 글은 Haskell 리스트에 대한 foldr과 foldl 함수만 다루고 있습니다. 부록에서는 다른 자료구조에 대한 함수도 이야기하는데(아마 Foldable 클래스의 인스턴스 구현을 말하는 것 같습니다), 또 하나의 커스텀 리스트 타입이 아니라 Map 같은 다른 타입에서 foldr과 foldl의 정의를 살펴보는 편이 더 유익했을 겁니다.
사실 이진 트리인 Map의 fold 정의를 살펴보는 쪽이 교육적으로 더 나은 출발점일지도 모른다고 생각합니다. 단일 연결 리스트는 본질적으로 왼쪽으로 치우쳐 있지만 이진 트리는 대칭이거든요. 그래서 이진 트리에서 foldr과 foldl의 구현은 훨씬 비슷합니다. 말 그대로 누적 함수의 인자 순서를 뒤집고 왼쪽과 오른쪽 자식을 맞바꾸면 됩니다. 게다가 누적 함수가 첫 번째 인자를 강제 평가하느냐 두 번째 인자를 강제 평가하느냐에 따라 지연 평가로 "조기 종료"하는 동작을 유도할 수도 있습니다. 그리고 foldr, foldl, foldr', foldl' 네 가지 모두 의미가 있습니다.
Haskell의 리스트는 꼬리 공유(tail sharing)가 가능한 단일 연결 리스트입니다.
CS 하는 사람에게 "순서"란 리스트의 배열을 뜻합니다. 하지만 그 밖의 거의 모든 사람은 연산의 시간적 순서를 떠올립니다. 그렇게 보면 정말로 오른쪽이나 왼쪽에서 "시작"하는 게 맞습니다.
지연되는 연산이 많아지면 그때부터 헷갈리기 시작하는 거죠.
AI가 foldl'과 foldr(특히 foldr), 그리고 Map에 대한 비슷한 버전들을 과하게 쓰는 걸 봤습니다. 같은 일을 더 단순하고 직관적으로 할 방법이 있는데도요.
AI가 복잡한 누적 함수로 foldr을 쓰면, 저는 AI에게 커스텀 모노이드 구조를 정의한 다음 foldMap을 쓰라고 시킵니다. 그러면 읽는 사람이 비대칭적인 누적 함수를 따라가지 않아도 되고, 매핑 연산과 결합 법칙을 따르는 결합 함수를 따로따로 생각하면 됩니다. 누적 함수가 하던 두 가지 일을 분리하는 건 가독성을 높이는 좋은 요령이고, 사람이 주로 코드를 읽는 입장이라면 아주 좋은 맞교환입니다.
정말 흥미롭게 읽었습니다. 몇 년 전에 처참하게 실패했는데, 다시 Haskell을 배워 보고 싶어지네요.
핵심 요약: foldl은 꼬리 재귀가 될 수 있다.
Hodl은 어때요?
비용이 foldl이나 foldr보다 훨씬 클 수 있어요.
수년 전에 제가 배운 건, foldr은 제 발등을 찍는 총(footgun)이고 제가 원했던 건 거의 틀림없이 foldl1'였다는 겁니다.
foldl(비엄격 버전)이 footgun이라는 말씀 아닌가요? 적어도 지연 언어에서 foldr이 어떻게 footgun이 되는지는 저로서는 떠오르지 않네요.