하스켈 리스트와 고차함수

앞서 리스트 기초 장에서는 리스트 타입의 정의와 head, tail, length 등 기본적인 리스트 함수들을 살펴보았습니다. 리스트는 이런 기본적인 함수 외에도 map, filter, foldr처럼 함수를 인자로 받는 함수들을 제공합니다. 하스켈에서는 함수가 다른 함수를 인자로 받거나 함수를 리턴할 수 있는데 이런 특성을 가진 함수들을 고차 함수(higher-order function)라고 부릅니다.

map 함수

우선 대표적인 고차 함수의 예로 map을 살펴보겠습니다. map의 타입은(a -> b) -> [a] -> [b]입니다. 타입 a를 받아 b를 리턴하는 함수 하나와 a 타입의 리스트 하나를 인자로 받아 b 타입의 리스트를 리턴하는 함수입니다. map은 주어진 함수를 리스트 각각의 원소에 적용하여 새로운 리스트를 리턴합니다. 간단한 사용 예는 다음과 같습니다.

> map (\x -> x + 1) [1,2,3]
[2,3,4]

여기서 \x -> x + 1은 하스켈에서 람다 함수(lambda function)을 정의하는 방법입니다.\를 사용하는 이유는 아스키 코드 중에서 그리스 알파벳 람다(λ)를 가장 닮았기 때문입니다.

이 람다 함수는 인자 x를 받아서 x + 1을 리턴합니다. ->를 기준으로 왼쪽은 인자, 오른쪽은 함수 몸통(function body)입니다. 인자가 2개 이상인 경우는 공백 문자로 구분해 주면 됩니다. 따라서 인자 xy를 받아 합을 리턴하는 함수는 \x y -> x + y로 정의할 수 있습니다.

앞서 하스켈 함수에서 배운 섹션(section)을 사용하면 같은 함수를 좀 더 간결히 표현할 수 있습니다. \x -> x + 1은 2개의 인자를 받는 (+) 연산자에 인자 하나만 먼저 적용하여 새로운 함수를 만들었다고 볼 수 있기 때문에 (+1)과 같이 표현할 수 있습니다.

> map (+1) [1,2,3]
[2,3,4]

filter

filter 함수는 각 원소에 대해 Bool을 리턴하는 테스트 함수(predicate)를 인자로 받아 각 원소 중에서 테스트를 통과한 원소들만 모아 새로운 리스트로 리턴하는 함수입니다.filter의 타입은 (a -> Bool) -> [a] -> [a]인데 첫 번째 인자 타입 a -> Bool을 보면 테스트 함수는 리스트의 원소 타입 a를 인자로 받아 Bool을 리턴하는 것을 확인하실 수 있습니다.

> filter odd [1,2,3,4,5]
[1,3,5]

filter와 비슷한 함수로는 partition 함수가 있는데, filter와 마찬가지로 테스트 함수를 받아 리스트 각 원소에 대해 테스트를 실시하는데, filter는 테스트를 통과한 원소의 리스트를 리턴하는 반면 partition은 테스트를 통과한 원소와 통과하지 못한 원소를 따로 모아 각각을 리스트로 리턴합니다.

리턴값이 2개의 리스트이므로 튜플을 사용합니다. 튜플의 첫 번째 원소는 테스트를 통과한 원소들의 리스트이고, 튜플의 두 번째 원소는 테스트를 통과하지 못한 원소들의 리스트입니다. partition 함수는 filter와 달리 Prelude 모듈에 정의되어 있지 않으므로 사용하려면 먼저 Data.List 모듈을 임포트해주어야 합니다.

> import Data.List
> partition odd [1,2,3,4,5]
([1,3,5],[2,4])

foldr

마지막으로 살펴볼 함수는 foldr입니다. 리스트의 경우 foldr의 타입은(a -> b -> b) -> b -> [a] -> b입니다. 알서 살펴본 map이나 filter와는 달리 리턴 타입이 [a]가 아니라 b임을 볼 수 있습니다. map처럼 리스트 각 원소를 가지고 새로운 리스트를 만들거나, filter처럼 리스트의 각 원소 중 일부를 추려서 새로운 리스트를 리턴하는 함수는 아님을 짐작할 수 있습니다.

이해를 돕기 위해 먼저 사용 예를 살펴보겠습니다. 다음은 foldr을 이용해 리스트 원소들의 합을 구하는 코드입니다.

> foldr (+) 0 [1,2,3,4,5]
15

(+)는 인자 두 개를 받아 합을 리턴하는 함수이고, 0은 초기값입니다. 위 foldr 함수를 풀어써보면 다음과 같습니다.

(1 + (2 + (3 + (4 + (5 + 0 )))))

리스트 기초에서 살펴본 리스트 [1,2,3,4,5]의 정의와 비교해보면 모양이 상당히 유사하다는 사실을 알 수 있습니다.

(1 : (2 : (3 : (4 : (5 : [])))))

리스트 정의에서 (:)(+)로 바뀌었고, []0으로 바뀌었습니다. 즉, foldr f acc의 의미는 리스트를 펼쳐놓고 (:)f[]acc로 바꾼 것과 같다고 생각할 수 있습니다.

이번에는 각 리스트의 곱을 구해보겠습니다.

foldr (*) 1 [1,2,3,4,5]

마찬가지로 리스트를 정의에 따라 풀어 쓰고 (:)(*)[]1로 바꿔쓰면 됩니다.

(1 : (2 : (3 : (4 : (5 : [])))))
(1 * (2 * (3 * (4 * (5 * 1 )))))

foldr을 이용하면 리스트의 길이를 리턴하는 length 함수도 구현할 수 있습니다. 아래 리스트 정의에서 (:)[]를 어떻게 바꾸면 각 원소 대신에 리스트의 길이를 계산하게 될지를 생각해 봅시다.

(1 : (2 : (3 : (4 : (5 : [])))))

금방 답이 떠오르지 않으신가요? 이해를 돕기 위해 이번에는 (:) 연산자를 infix가 아닌 prefix로 표기해보겠습니다.

(:) 1 ((:) 2 ((:) 3 ((:) 4 ((:) 5 []))))

(:)를 보기 좋게 임의의 함수로 f로 대체하면 다음과 같습니다.

f 1 (f 2 (f 3 (f 4 (f 5 []))))

이제 함수 f를 어떻게 정의하면 리스트의 길이를 구할 수 있을까요? 길이를 구할 때 리스트의 원소가 무엇인지는 중요하지 않으므로 첫 번째 인자를 무시합니다. 그리고 f 함수가 매번 호출될 때마다 리스트의 길이가 1만큼 늘어난다는 사실에 착안하여 두 번째 인자로 넘어온 값에 1을 더해주면 어떨까요? 그렇게 f를 정의하면 \x y -> y + 1가 되는데, 실제로 테스트해보면 리스트의 길이를 리턴하는 것을 볼 수 있습니다.

> foldr (\x y -> y + 1) 0 [1,2,3,4,5]
5

foldr 함수는 맥가이버 칼로 불릴 만큼 굉장히 강력한 함수입니다. foldr 함수를 이용하면 map이나 reverse 함수도 구현할 수 있습니다.

숙제: foldrmapreverse를 구현해 봅시다.

One thought on “하스켈 리스트와 고차함수

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s