오늘 공부한 건 하스켈의 두 번째 허들인 폴드야.

첫 번째는 타입 클래스였는데, 폴드는 허들 높이로 보면 타입 클래스만큼은 아님.

하지만 폴드 함수로 시작되는 고차 함수 전반에 대한 이해라는 측면에서 중요도는 비슷한 것 같음.

무엇보다도 폴드는 기본기거든.


폴드는 reduce, accumulate, aggregate, compress, inject등의 이름을 갖는 다른 언어의 함수들과 유사해.


간단하게 말하면, f, a, xs를 인자로 받는데,

f: binary function

a: initial accumulator

xs: list

라고 할 때,

f를 a와 head xs에 적용

-> 이 결과값과 xs의 두 번째 원소에 f를 적용

-> 또 결과값이 나오고 이것과 세 번째 원소에 f를 적용

-> 반복..

-> last xs까지 진행한 최종 결과가, 폴드의 결과값이다.


이것이 foldl 함수의 적용 메커니즘이야.

foldr은 시작 순서가 오른쪽 리스트의 끝인 last xs부터라는 점, 그리고 f가 accumulator를 두 번째 인자로 받는다는 점이 다름.


폴드가 왜 중요하냐면, 함수형으로 반복 작업을 처리하는 기본 방법이 폴드라서 그래.

가장 먼저 보는 예제는 재귀 정의를 폴드로 다시 쓰는거고,

이외에도 Prelude 함수들을 폴드로 다시 쓰는 예제들이 많이 나오는데,


sum = foldr (+) 0

product = foldr (*) 1


이런 간단한 것부터 시작해서..


reverse = foldl (flip (:)) []

reverse = foldr (flip (++) . return) []

length = foldl (const . (1+)) []

length = foldr (const (i+)) []

head = foldr1 const

last = foldl1 (const id)


이런 포인트 프리 스타일도 나오고..


map f = foldr (\x a -> f x : a) []

filter p = foldr (\x a -> if p x then x : a else a) []


이렣게 폴드와 동급 위상인 줄 알았던 map과 filter 까지 폴드로 구현할 수 있음을 알게 된다.

map과 filter 구현 코드에서 f, p가 자유 변수인 것 보이지? 저 람다들은 클로저임.


폴드는 하스켈을 공부하는 내내 쓰게될, 하스켈의 for문 같은 거라고 보면 됨.

그러니 익숙해질 수 있게 많이 연습하자.