Functional Programming - Higher-Order Functions
실은 우리는 이미 higher-order function 을 사용해 보았습니다. 여기서 higher-order function이 무엇인지 알아보겠습니다.
A function is called higher-order if it takes a function as an argument or returns a function as a result.
함수를 매개변수로 받거나 또는 결과로 돌려주는 함수를 의미하는데요, 아래 예의 twice 도 함수를 매개변수로 받기때문에 higher-order function 이라고 이야기 할 수 있습니다.
twice :: (a -> a) -> a -> a
twice f x = f (f x)
또한, 여기서 눈에 보이는 점은 twice 가 (a -> a) 와 같이 괄호(parentheses)를 이용하여 함수를 매개변수로 받는 것을 표현하였습니다. 오른쪽의 경우도 (a -> a) -> (a -> a)와 같이 표현 할 수 있습니다.
그럼 이러한 higher-order function이 왜 유용할까요?
- 프로그래머는 중복으로 함수를 구현하는 것을 좋아하지 않습니다. 따라서, 반복(repetition)적인 pattern을
higher-order function에 적용하고, 다양한 함수를 인자로 받아 처리하게끔 합니다. (위의twice를 보게되면 함수를 인자로 받음으로써 함수에 따라 동작이 다르지만, 두번씩 호출되는 pattern을 유지하게 됩니다.) 또한,
higher-order function들로 domain-specific language 를 정의할 수있다는 것입니다.A domain-specific language (DSL) is a computer language specialized to a particular application domain. This is in contrast to a general-purpose language (GPL), which is broadly applicable across domains, and lacks specialized features for a particular domain.1
마지막으로
higher-order function의 대수학적인 속성(Algebraic properties) 때문입니다. 첫번째 이유와 비슷하게 수학적으로 다양한 입력에 대해 처리를 가능하게 하기 때문입니다. 함수가 일반적으로(general) 사용할 수 있게되는 특성을 부여하게 됩니다.
The Map Function
앞선 twice 는 다소 사용용도에 의문을 가지게 하였습니다. 하지만 앞으로 다루게 될 map 은 자주 사용하게 되는 중요한 함수입니다. map 은 함수와 list를 인자로 받아 list 내 모든 element 에게 순차적으로 인자로 받은 함수를 적용합니다.
map :: (a -> b) -> [a] -> [b]
한가지 중요한 것은 위 map 의 type에서 보이듯 map 은 다소 사용자에게 좁은 선택을 제공합니다. 다시말해 a type이 b type으로 전환되는 함수에 맞춰 list의 모든 element는 a type이어야 합니다. 반대의 경우도 마찬가지겠죠. 예를 보겠습니다.
> map (+1) [1,3,5,7]
[2,4,6,8]
list의 모든 element에 대해 (+1) 이 적용된 것을 볼 수 있습니다.
map 은 list comprehension (이전 포스팅2 참조)을 이용하여 쉽게 구현할 수 있습니다.
map f xs = [f x | x <- xs]
또는 recursive function 으로 구현할 수 있습니다.
map f [] = []
map f (x:xs) = f x : map f xs
recursive function 의 경우 이후 배우게 될 super higher-order function 에 적용할 수 있습니다. 예를 들어 fold 함수들이 있습니다. (아직은 저도 이해가 안가지만 강의를 들으면서 추가 설명하도록 하겠습니다. fold 는 함수 중 하나로 내부에 recursive function 을 이용하는 것으로 생각됩니다.)
The Filter Function
다른 종류의 higher-order function 인 filter 를 보겠습니다. filter 는 list의 모든 element에 대해 함수를 만족하는 경우만을 합쳐 돌려줍니다.
filter :: (a -> Bool) -> [a] -> [a]
위와 같이 인자로 받는 함수는 Bool 값을 리턴하고, 이를 이용하여 list를 재구성합니다.
> filter even [1..10]
[2,4,6,8,10]
위의 예와 같이 even 은 인자로 받은 Interger 에 대해 짝수이며 True, 아니라면 False 를 돌려주는 함수로 filter 함수에 따라 list의 모든 element를 체크하게 됩니다. map 과 동일하게 아래 두가지 방법으로 구현할 수 있습니다.
filter p xs = [x | x <- xs, p x]
filter p [] = []
filter p (x:xs)
| p x = x : filter p xs
| otherwise = filter p xs
list comprehension 을 이용한 경우가 훨씬 쉽지만, recurvice function 의 경우 또한 어렵지 않게 이해할 수 있습니다.
우리는 지금까지 higher-order function 의 예로 map 과 filter 를 봤습니다. 두 함수 모두 list에 대해 재귀적으로(recursively)으로 접근하며 결과를 얻었습니다. 이러한 동작을 하는 대표적인 함수 중 foldr 또는 foldl 이 있습니다. 여기서 r 과 l 은 방향을 이야기 합니다. 예를 들어, foldr 은 오른쪽(right)에서 접어들어간다는 의미입니다.
The Foldr Function
list를 매개로 하는 많은 함수들이 아래와 같은 재귀(recursion) 패턴에 의해 구현되어 있습니다.
f [] = v
f (x:xs) = x (+) f xs
위를 설명하면, 비어있는 list에 대해서는 v를 돌려줍는다. 이외에 list가 비어있지 않은 경우 tail xs 에 대해 재귀적으로(recursively) 함수 f 를 적용하고, 이를 head x 와 (+) 을 하게 됩니다. 동작을 머리속에서 상상하게 되면 재귀부분인 f xs 는 계속해서 tail을 찾게 되고 결국 비어있는 리스트를 돌려주며 마치 오른쪽에서 접어지며 결과를 받아오는 모습 이 됩니다. 다음 예를 보겠습니다.
sum [] = 0 -- v = 0
sum (x:xs) = x + sum xs -- (x) = +
product [] = 1 -- v = 1
product (x:xs) = x * product xs -- (x) = *
and [] = True -- v = True
and (x:xs) = x && and xs -- (x) = &&
위의 함수들을 아래와 같이 foldr 을 이용하여 표현할 수 있습니다.
sum = foldr (+) 0
product = foldr (*) 1
or = foldr (||) False
and = foldr (&&) True
그럼 foldr 은 어떻게 구현할 수 있을까요? 재귀를 이용하여 구현하면 다음과 같습니다.
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f v [] = v
foldr f v (x:xs) = f x (foldr f v xs)
위에서 설명한 것과 크게 다르지 않은 것을 볼 수 있습니다. 다음 예를 보면서 동작을 이해해봅시다.
sum [1,2,3]
= foldr (+) 0 [1,2,3]
= foldr (+) 0 (1:(2:(3:[])))
= 1+(2+(3+0)) -- replace each (:) by (+) and [] by 0.
= 6
많은 부분이 생략되었지만, 위의 설명과 크게 다르지 않습니다. list를 cons(:)를 이용하여 분해하고 이를 뒤부터([ ]) 적용한다는 점이 어떠한 함수에서도 동일하게(homomorphism) 적용될 겁니다.
Other Foldr Examples
foldr 를 이용하여 더 많은 함수를 정의할 수 있습니다. 먼저 length 함수를 보겠습니다.
length :: [a] -> Int
length [] = 0
length (_:xs) = 1 + length xs
위의 정의에서 _ (underscore)를 이용한 부분이 눈에 갑니다. 이유는 length 함수에 있어서 x 를 이용하지 않기때문입니다. 다음 예는 length 의 동작 예입니다.
length [1,2,3]
= length (1:(2:(3:[])))
= 1+(1+(1+0)) -- replace each (:) by \_ n -> 1+n and [] by 0
= 3
따라서 우리는 foldr 을 이용하여 정의할 수 있습니다.
length = foldr (\_ n -> 1+n) 0
(자세한 설명은 haskell foldr length - StackOverFlow 참고 바랍니다.) 다른 예를 더 보겠습니다.
reverse [] = []
reverse (x:xs) = reverse xs ++ [x]
위 reverse 의 경우도 재귀를 통해 표현하였습니다. 하지만 이전과는 다르게 오른쪽이 아닌 왼쪽에서 재귀가 일어나고 있는 점이 다릅니다.
reverse [1,2,3]
= reverse (1:(2:(3:[])))
= (([] ++ [3]) ++ [2]) ++ [1] -- replace each (:) by \x xs -> xs ++ [x] and [] by [].
= [3,2,1]
하지만, length 의 경우와 동일하게 lambda를 통해 처리하면 됩니다. 따라서 다음과 같이 정의할 수 있습니다.
reverse = foldr (\x xs -> xs ++ [x]) []
또한, 위의 (++) 도 아래와 같이 정의할 수도 있습니다.
(++ ys) = foldr (:) ys -- replace each (:) by (:) and [] by ys.
그럼 이런 foldr 이 왜 유용할까요?
일단 리스트에 대해 적용되는 함수, 예를 들어 sum 과 같은 함수를 foldr 을 통해 표현하기가 쉽기 때문입니다. 또한, foldr 을 통해 구해진 list에 재차 적용을 하는 등 다양한 함수를 순차적으로 적용할 수 있습니다. 따라서 프로그램이 최적화(optimization)될 수 있습니다.
Other Library Functions
추가적으로 haskell library가 제공하는 함수들을 보겠습니다. 그 중 하나인 composition 함수는 다른 functional progamming 언어에서도 기본이 되는 함수로, 두가지 함수를 하나의 함수로 합칩니다.
(.) :: (b -> c) -> (a -> b) -> (a -> c)
f . g = \x -> f (g x)
(.)은 다른 Object-Oriented 언어에서는 Method를 부르는 기능인 반면, haskell에서는 composition 을 의미합니다.
위의 type 구현은 다소 복잡하게 느껴집니다. 두번째 함수의 결과가 첫번째 함수의 입력값으로 들어가 순서가 바뀐 것처럼 보이기 때문입니다. 하지만 바로 아래의 함수 구현을 보면 이해가 됩니다. 입력값 x 를 g 에 적용하고 그 결과를 다시 f 에 적용하기 때문입니다. 아래의 예를 보면 이해가 쉽습니다.
odd :: Int -> Bool
odd = not . even
odd 는 매개변수가 홀수인지 검사하는 함수로 위와 같이 not . even을 이용하여 구현이 가능합니다. 먼저 even 이 적용되고 그결과를 다시 not 에 적용하는 것을 볼 수 있습니다.
이러한 (.)를 이용하여 코딩을 하는 것은 다른 개발자가 해석하는데 어려움을 줄 수 있습니다. 따라서, 연습을 위해서는 (.)을 자주 사용해야하지만, 실제 개발에서는 필요한 상황에서만 사용하는 것이 좋습니다. 물론 (.)이 사용된 코드를 해석해주는 프로그램도 있지만, 자신이 생각하는 만큼 다른 개발자들도 그 코드가 멋지다고 생각안 할 수 있다는 점을 명심해야합니다. :)
계속해서 다른 함수를 찾아보겠습니다.
all :: (a -> Bool) -> [a] -> Bool
all p xs = and [p x | x <- xs]
> all even [2,4,6,8,10]
True
위의 경우는 list comprehension을 이용하여 구현한 all 함수 입니다. 저를 포함한 많은 개발자들이 list comprehension의 경우가 더 쉽게 느껴질 수도 있습니다. 하지만, foldr 의 경우 list comprehension과 달리 list를 포함한 재귀 형태를 갖출 수 있는 모든 data type에 적용이 가능합니다. 따라서, foldr 또는 앞으로 배울 foldl 에 익숙해지는 것이 바람직할 것 같습니다.
추가적으로 다른 함수들을 보겠습니다.
any :: (a -> Bool) -> [a] -> Bool
any p xs = or [p x | x <- xs]
> any isSpace "abc def"
True
takeWhile :: (a-> Bool) -> [a] -> [a]
takeWhile p [] = []
takeWhile p (x:xs)
| p x = x : takeWhile p xs
| otherwise = []
> takeWhile isAlpha "abc def"
"abc"
dropWhile :: (a -> Bool) -> [a] -> [a]
dropWhile p [] = []
dropWhile p (x:xs)
| p x = dropWhile p xs
| otherwise = x:xs
> dropWhile isSpace " abc"
"abc"
위의 함수를 포함해서 앞서 배웠던 map, filter 모두 foldr을 이용해서 구현해보시기 바랍니다.