import Prelude hiding (foldr)
함수형 언어는 '고차 함수'와 '지연 연산' 이라는 강력한 모듈화 도구를 제공해준다. 이 둘은 glue 역할을 하여 새로운 형태의 모듈화를 가능하게 한다.
어떻게 glue 역할을 하는지 살펴보자.
data List a = Nil | Cons a (List a) deriving (Show, Eq)
타입변수(a
)로 정의된 리스트 타입이다. 단일연결리스트(singly linked list)이며, 빈 경우(Nil
)와 머리-꼬리를 나타내는 Cons
중 하나(|
)라는 의미이다.
Nil -- []
Nil
Cons 1 (Cons 2 (Cons 3 Nil)) -- [1, 2, 3]
Cons 1 (Cons 2 (Cons 3 Nil))
리스트 요소들의 합을 구하는 함수 sum
는 각각의 경우에 대해 정의되어야 한다.
sum Nil = 0
sum (Cons num rest) = num + sum rest
빈 리스트의 합은 0이고, Cons
의 경우에는 머리(num
)를 나머지 합(sum rest
)에 더하면 된다.
sum (Cons 1 (Cons 2 (Cons 3 Nil)))
6
이 정의에서 0
과 +
만 빼면 리스트 요소들로 무언가를 할 수 있는 재사용 가능한 패턴이 만들어진다.
sum = foldr (+) 0
(foldr f x) Nil = x
(foldr f x) (Cons a l) = f a ((foldr f x) l)
sum (Cons 1 (Cons 2 (Cons 3 Nil)))
6
하스켈에서 리스트는 이미 정의되어 있으며 Nil
은 []
, Cons
는 (:)
를 사용할 수 있다. 이제부터는 하스켈의 리스트를 직접 이용한다. (sum
과 foldr
도 이미 정의되어 있지만, 이건 이 글에서 설명하려는 내용이니 재정의하겠다.)
foldr f x [] = x
foldr f x (a:as) = f a (foldr f x as)
((foldr f x) as)
나 (foldr f x as)
는 같다. 하스켈에서는 함수에 인자를 하나씩 적용하며, 인자가 2개 필요한 함수에 하나만 적용하면 그 결과는 인자를 하나 필요로 하는 함수가 된다.
sum
을 foldr
, (+)
, 0
의 결합으로 표현하는 과정에서 foldr
이라는 부산물이 나왔는데, 이는 다양하게 활용된다.
sum = foldr (+) 0
product = foldr (*) 1 -- 리스트 요소 곱
anytrue = foldr (||) False -- 리스트 요소 중 True가 있나?
alltrue = foldr (&&) True -- 리스트 요소 중 False가 있나?
foldr f x
는 Cons
를 f
로, Nil
을 x
로 대체하는 것. Cons a (Cons b Nil)
은 f a (f b x)
와 같다. 따라서 foldr (:) []
는 원래의 리스트를 그대로 복사하는 함수가 된다.
원래의 리스트 요소들에 모두 2를 곱하는 함수 doubleall
을 정의해보자.
doubleall = foldr f []
where f a x = (a*2) : x
그런데...
f a x = (a*2) : x
f a x = (:) (a*2) x
f a = (:) (a*2)
f a = (:) ((*2) a)
f a = ((:) . (*2)) a
f = (:).(*2)
여기서 (.)
는 함수 합성 연산자. (f . g) x = f (g x)
이다.
doubleall = foldr ((:).(*2)) []
doubleall [1,2,3]
[2,4,6]
sum
에서 (+)
과 0
을 추출하여 일반화한 것처럼, doubleall
에서도 곱하기 2 부분((*2)
)만 추출하여 일반화하면 map
이란 함수를 얻을 수 있다.
doubleall = map (*2)
map f = foldr ((:).f) []
doubleall [1,2,3]
[2,4,6]
행렬 요소들의 합을 구하는 함수를 보자.
summatrix = sum . map sum
summatrix [[1,2,3],
[4,5,6],
[7,8,9]] -- 행렬을 리스트의 리스트로 표현.
45
하스켈에는 이미 foldr
과 map
이 정의되어 있다.
여기서 다룰 트리 예제는 자식을 여럿 가질 수 있는 트리다. 각 노드에는 a
값의 레이블이 있고, 자식 트리는 리스트로 표현된다.
data Tree a = Node a [Tree a] deriving (Show)
다음의 트리는 ..
아래의 코드로 표현된다.
t1 = Node 1
[Node 2
[],
Node 3
[Node 4
[]]]
트리에 대해서도 리스트의 foldr
과 map
에 해당하는 함수들을 만들어 볼 수 있다. 리스트에서는 sum
함수에서부터 일반화하는 방향으로 출발했지만 이번에는 foldr
을 참고하여 바로 만들어보겠다.
foldr
이 Nil
과 Cons
에 대해 각각 대체 값을 인자로 받은 것과 마찬가지로 foldtree
는 Node
와 Nil
과 Cons
을 대체하는 인자가 3개 필요하다.
foldtree f g a (Node label subtrees)= f label (foldr g a (map (foldtree f g a) subtrees))
maptree f = foldtree (Node . f) (:) []
이 함수들을 이용하면 리스트에서와 마찬가지로 트리를 처리하는 함수를 쉽게 만들 수 있다.
sumtree = foldtree (+) (+) 0
labels = foldtree (:) (++) []
sumtree t1
10
labels t1
[1,2,3,4]
어떤 데이터 타입을 만들더라도 foldr
이나 foldtree
와 같은 '고차 함수'를 만들면 쉽게 새로운 함수를 만들어낼 수 있다.