Haskell 블로그, foldl과 foldr 차이 설명 재게재: 지연 평가에서 foldl이 thunk 사슬로 공간을 선형으로 늘림
- foldl과 foldr은 리스트를 왼쪽에서 오른쪽으로 같은 순서로 순회하며, 차이는 결합 방향임. foldl은 ((0 + 1) + 2) + 3처럼 왼쪽 결합, foldr은 1 + (2 + (3 + 0))처럼 오른쪽 결합임
- 엄격한 언어에서 foldl은 꼬리 재귀로 상수 공간에서 축약되지만, foldr은 축약을 시작하기 전에 리스트 길이 n만큼 스택 프레임을 쌓아야 함
- Haskell 같은 지연 언어에서 게으른 foldl은 ⟨⟨⟨0 + 1⟩ + 2⟩ + 3⟩ 형태의 thunk 사슬을 만들어 입력 길이에 선형인 공간을 쓰고, 상수 공간에서 스트림을 처리하던 코드를 선형 공간 알고리즘으로 바꿔버림
- foldl'은 다음 원소로 넘어가기 전에 누산기 thunk를 강제해서, (+) 한 번보다 큰 thunk를 만들지 않고 상수 공간에서 리스트를 순회함
- 이 글은 2019년 hasura/graphql-engine PR 논의에서 나온 Alexis King의 설명을 편집자 노트와 함께 Haskell 블로그에 재게재한 것임
Hacker News opinions
foldr은 각 단계마다 제어 흐름을 누산 함수에 통째로 넘김. 그래서 foldl'이나 중간에 빠져나오는 순회도 foldr로 구현할 수 있음
그 정도면 그냥 재귀 함수를 명시적으로 쓰는 게 낫지 않나. go [] = ... go (h:t) = ... 이렇게 쓰면 되는데 fold로 꼬아서 만들 이유가 있나 싶음
AI가 foldl'과 foldr을 진짜 남발함. Map에도 마찬가지고. 복잡한 누산 함수로 foldr 쓴 코드를 보면 monoid 구조 정의하고 foldMap 쓰라고 프롬프트함. 매핑 연산과 결합 연산을 분리하면 읽는 사람이 덜 고생함
AI한테 코드 맡기면 Haskell 쓰는 사람이라는 자랑거리가 좀 무색해지는 거 아님?
CS 하는 사람한테 ordering은 리스트 배열 순서인데, 나머지 사람은 시간 순서로 받아들임. 그래서 왼쪽이나 오른쪽에서 시작한다고 느끼고, 지연 연산이 많아지면 더 헷갈림
둘 다 왼쪽에서 오른쪽으로 순회한다는 설명은 단일 연결 리스트를 가정할 때만 맞음. 엄격한 언어에서 배열이나 이중 연결 리스트로 구현하면 foldr은 오른쪽에서 왼쪽으로 감. Haskell 리스트가 왼쪽으로만 순회할 수 있어서 두 구현이 그렇게 된 거지
맞음. 글은 Haskell 리스트의 foldr, foldl 함수만 다룸. 배우는 입장에서는 Map 같은 다른 타입 정의를 먼저 보는 게 낫다고 봄. 이진 트리는 대칭이라 foldr과 foldl 구현이 인자 순서만 바꾸는 수준이고, 누산 함수가 첫 인자를 강제하느냐 두 번째를 강제하느냐로 조기 종료도 만들 수 있음. foldr, foldl, foldr', foldl' 네 가지가 다 의미 있음
Haskell 리스트는 꼬리 공유가 가능한 단일 연결 리스트임