[Haskell Tutorial] High Order Function

 

이번 포스트는 http://learnyouahaskell.com/higher-order-functions 에 근거하고 있습니다.

 

📌 고차함수 (High Order Function)

고차함수 는 함수를 파라미터로 넘겨줄 수 있고, 반환값으로도 사용할 수 있습니다.

한마디로 함수를 값으로 취급할 수 있다는 것을 의미합니다.

 

📌 커링 (Currying)

Haskell 다중인자 함수의 정체

하스켈의 함수는 하나의 인자만 받을 수 있도록 되어있는데,

어떻게 여러개의 인자를 받는 함수를 구현할 수 있는 것일까요?

두 인자를 받아 큰 값을 반환하는 함수 max 는 다음과 같이 두 단계로 나눠볼 수 있습니다.

 

ghci> max 4 20
20

{- ✅ 위 표현식은 다음과 같이 분리할 수 있다. -}

ghci> maxValueWith4 = max 4
ghci> maxValueWith4 20
20

 

위와 같이 Haskell 에서 다중 인자 함수는 사실 여러개의 커링 함수로 구성 됩니다.

 

커링과 부분적용

커링(currying) 은 n 개의 인자를 받는 함수를 n개의 단항 함수로 변환하는 것입니다.

n개의 단항함수 각각은 그 다음 체인의 함수를 반환하기 때문에 여기서 고차함수 가 등장합니다.

커링 을 활용하면 부분적용 통해서 n 개의 인자를 모두 제공받을 때까지 실행을 지연시킬 수 있습니다.

부분적용 은 필요한 인자들 중 일부만 적용된 함수입니다.

대표적으로 Haskell 의 prefix function 을 예시로 들 수 있습니다.

 

ghci > :type (+3)
(+3) :: Num a => a -> a

{- 위 표현식은 3을 더하는 함수를 반환한다. -}

 

커링과 부분적용의 차이

엄밀히 말하자면 두 개념은 유사하지만 동작방식에 차이가 있습니다.

커링 은 엄격한 부분적용 의 한가지 방법이라고 볼 수 있을 것 같습니다.

• 커링 : 체인의 다음 함수를 반환합니다.
• 부분적용 : n개의 인수를 가지는 함수에서 n-m 개의 인수를 받는 하나의 함수를 반환합니다.

인수가 두개라면 동일하게 동작하겠지만, 그 이상의 인수를 가지는 함수라면 동작 방식이 달라집니다.

 

예를 들어 func 이 x, y, z 라는 인수를 받는다면,

커링은 3개의 단항 함수를 반환하여 결과적으로 func(x)(y)(z) 의 체인 구조로 호출되고
부분적용은 x 를 인수에서 제외할 경우 func(y, z) 로 호출합니다.

 

정리하자면, 고차함수의 의의는?

함수형 프로그래밍에서는 고차함수를 이용해서 공통된 패턴을 추상화 할 수 있습니다.

이를 통해 재사용성 이 높아지며 가독성 이 좋은 함수를 설계할 수 있습니다.

명령형 프로그래밍에서는 같은 방식을 위해서 반복문, 조건문, 변수등을 함수로 이를 감싸 구현합니다.

또한 부분적용 을 활용하면 호출시점을 해당 값이 필요한 시점까지 지연 시킬 수 있다는 장점이 있습니다.

 

📌 람다 함수

람다 함수는 익명함수입니다. 말 그대로 이름이 없는 함수 입니다.

Haskell 에서는 다음과 같이 사용할 수 있습니다.

 

\x -> x + 1

 

왜 람다함수를 사용할까요?

람다함수는 특정 이유로 한번 사용하고 말 함수에 유용하며

때문에 주로 HOF 의 인자로 함수를 넘길때 람다함수를 사용합니다.

만약 람다함수가 없다면, 다음과 같이 where block 을 이용하여 구현할 수 있습니다.

 

ghci> addOneMap arr = map addOne arr where addOne x = x + 1
ghci> addOneMap [1,2,3]
[2,3,4]

 

람다함수를 이용하면 다음과 같이 표현할 수 있습니다.

 

addOneMap arr = map (\x -> x + 1) arr

 

람다함수를 통해 타입선언 형태와 더 가깝게 함수 표현하기

저서에 소개된 람다함수를 이용한 흥미로운 예제가 있습니다.

세 인자를 더하는 함수 addThree 는 다음과 같이 표현할 수 있습니다.

 

addThree :: (Num a) => a -> a -> a -> a  
addThree x y z = x + y + z  

 

Haskell 의 모든 함수는 기본적으로 커링함수이기 때문에 위 표현식은 다음과 동일합니다.

 

addThree :: (Num a) => a -> a -> a -> a  
addThree = \x -> \y -> \z -> x + y + z

 

람다함수를 이용한 표현식이 타입선언과 좀 더 가까운 형태이지만, 읽기 쉬운 형태는 첫번째 표현식이기 때문에

보통 이렇게까지 표현하지는 않습니다.

 

📌 fold 와 scan 함수

fold 와 scan 는 함수형 프로그래밍에서 map, filter 와 함께 가장 자주 활용되는 함수입니다.

두 함수 모두 순회를 하는 방향에 따라 left side 와 right side 로 구분됩니다.

이 두 함수 모두 다음 세가지 요소로 구성됩니다.

 

• binary function
• starting value
• fold 할 대상 list

 

수학에서 binary function(이진 함수) 란 두 개의 입력을 받는 함수를 의미합니다.

 

 

보다 정확히 해석하자면 서로 다른 두 집합 X, Y 의 데카르트 곱의 결과인 Z 를 만족시키는 함수입니다.

먼저 fold 함수를 살펴보겠습니다.

 

foldl, foldr 살펴보기

fold 함수는 리스트 순회 방향에 따라 foldl, foldr 로 구분됩니다.

여기서 foldl 은 -> 방향, foldr 은 <- 방향입니다.

이 함수를 활용하는 방법을 알아보기 위한 간단한 예시로 maximum 함수를 구현해보겠습니다.

해당 함수는 인자로 주어진 리스트의 요소 중 가장 큰 값을 반환합니다.

 

ghci> maximum' (x:xs) = foldr (\x acc -> max x acc) x xs
ghci> maximum' [2, 10, 11, 4]
11

 

앞서 설명한 람다 함수를 foldr 의 binary function 으로 넘겨주고

starting value 는 패턴 매칭을 통해 배열의 첫번째 요소로 지정합니다.

여기서 foldr1 를 이용하면 함수를 더 간단하게 만들 수 있습니다.

이 함수는 starting value 를 배열의 첫번째 요소에서 가져옵니다.

이를 통해 패턴매칭을 제거할 수 있습니다.

 

ghci> maximum' arr = foldr1 (\x acc -> max x acc) arr

 

앞서 살펴보았듯이 max 또한 커링 함수이기 때문에 람다함수를 없애고 다음과 같이 나타낼 수 있습니다.

 

ghci> maximum' arr = foldr1 max arr

 

여기에 eta conversion 을 사용하면 함수의 매개변수를 제거할 수 있습니다.

이를 통해 point free style 함수를 구현할 수 있습니다.

 

ghci> maximum' = foldr1 max

 

💡 (참고) eta conversion

람다 대수(lambda calculus) 의 rewrite rules 중 하나입니다.

 

 

1. \x -> abs x

{- 1. 에서 2. 로 변형하는 것을 eta reduction, 그 반대를 eta expansion 이라고 합니다. -}

2. abs

 

Eta conversion

Eta conversion - HaskellWiki

What does eta reduce mean in the context of HLint

 

그외에 foldl, foldr 를 이용한 다양한 예시

map 과 filter 도 fold 함수로 구현 가능합니다.

 

ghci> map' f = foldr (\x acc -> f x : acc) []
ghci> map' (*3) [1, 2, 3]
[3,6,9]

ghci> filter' p = foldr (\x acc -> if p x then x : acc else acc) []
ghci> filter' (>10) [11, 9, 2, 130, -1]
[11,130]

ghci> reverse' = foldr (\x acc -> acc ++ [x]) []
ghci> reverse' [1, 2, 3]
[3,2,1]

ghci> reverse' = foldl (\acc x -> x : acc) []
ghci> reverse' [1, 2, 3]
[3,2,1]

 

여기서 foldl 을 활용한 reverse 예시는 다음과 같이 축약할수도 있습니다.

왼쪽에서부터 순회하기 때문에 binary function 의 두 인자 acc 와 x 를 붙인 다음,

이를 뒤집으면(flip) 동일한 결과를 얻을 수 있습니다.

 

ghci> reverse' = foldl (flip (:)) []

 

foldl vs foldr

foldl 과 foldr 은 infinite list 를 다루는 관점에서 차이가 존재합니다.

[x1, x2, x3, ...] 의 리스트에 함수 f 를 적용하고 초기값이 z 라고 한다면,

각각의 함수는 다음과 같은 형태를 가집니다.

 

{- foldl (left associative) -}

f ( ... (f (f (f (f z x1) x2) x3) x4) ...) xn

{- foldr (right associative) -}

f x1 (f x2 (f x3 (f x4 ... (f xn z) ... )))

 

두 함수 모두 lazy 하게 평가된다는 것은 동일합니다.

다만 위에서 볼 수 있듯이 foldl 은 결과 값을 얻기 위해 중첩된 모든 리스트를 탐색해서

최종 표현식을 만들어야하기에 이는 곳 stack overflow 를 발생시키게 됩니다.

반면 foldr 은 f 가 적용된 하나의 요소 + 나머지 infinite list 로 분리하여 적용 가능하기 때문에

문제없이 동작하게 됩니다.

 

foldl versus foldr behavior with infinite lists

foldl versus foldr behavior with infinite lists

Haskell, foldr on infinite list

Haskell, foldr on infinite list

 

scanl, scanr 살펴보기

이 두 함수는 앞서 설명한 fold 함수와 크게 다르지 않습니다.

차이점은 scan 함수는 중간 누적값들을 결과 배열에 포함시켜준다는 것입니다.

 

ghci> scanl (+) 0 [1, 2, 3, 4]
[0,1,3,6,10]

ghci> scanr (+) 0 [1, 2, 3, 4]
[10,9,7,4,0]

 

순회를 하는 방향에 따라 최종 결과값이 담기는 위치가 달라집니다.

fold 과정이 어떻게 이루어지는지 확인할 때 유용할 것 같습니다.

 

📌 Function application with $

Haskell 에서 일반적으로 함수는 left-associative 합니다.

따라서 다음코드의 결과는 15 입니다.

 

ghci> sqrt 4 + 4 + 9
15.0

-- 위 표현식은 다음과 동일합니다.

ghci> (((sqrt 4) + 4) + 9)
15.0

 

만약 4+4+9 의 제곱근을 구하고 싶다면 다음과 같이 괄호를 사용해서

연산의 우선순위를 부여해야할겁니다.

 

ghci> sqrt (4 + 4 + 9)
4.123105625617661

 

이럴때 가장 낮은 연산자 우선순위를 가지는 $ 를 이용하면

right-associative 한 연산을 깔끔하게 수행할 수 있습니다.

이를 통해 양옆에 괄호를 사용하는 것과 동일한 동작을 구현할 수 있습니다.

 

ghci> sqrt $ 4 + 4 + 9 -- ✅ 이거는 sqrt (4 + 4 + 9) 와 동일하다
4.123105625617661 -- 17 의 제곱근

 

📌 합성 함수

합성함수 표현

합성함수는 다음과 같이 표현합니다.

 

 

즉 두 함수 g, f 가 연쇄적으로 호출될 때 h 를 g 와 f 의 합성함수 라고 표현합니다.

Haskell 에서 합성함수는 다음과 같은 타입을 가집니다.

 

ghci> :type (.)
(.) :: (b -> c) -> (a -> b) -> a -> c

 

우리는 이미 함수가 left-associative 하다는 것을 알고 있습니다.

따라서 위 타입은 다음과 같이 표현할 수 있을 것입니다.

 

(.) :: (b -> c) -> (a -> b) -> (a -> c)

 

타입을 다시 보면 2개의 함수를 인자로 받아 새로운 함수를 반환하는 것으로 보이지 않나요?

이를 도식화하면 다음과 같습니다.

 

 

a 라는 제네릭 타입이 c 라는 제네릭 타입으로 바뀌기 위해

두 개의 함수 g 와 f 를 거치며 이는 h 라는 새로운 함수를 통해 이루어진다는 것을 알 수 있습니다.

 

합성함수의 쓰임새

합성함수는 람다함수로 넘겨주던 것을 좀 더 직관적인 형태 로 바꾸는데 유용합니다.

예시를 위해 다음과 같은 함수가 있다고 하겠습니다.

 

ghci> map (\xs -> negate (sum (tail xs))) [[1..5],[3..6],[1..7]]  
[-14,-15,-27]

 

이 함수는 원소 배열의 첫번째 요소(head) 를 제외한 나머지 값들의 합의 음수값 배열을 만들어 반환합니다.

이제 이 함수를 합성함수를 이용해서 간단하게 표현해보겠습니다.

먼저 합성함수의 정의를 다시 한번 살펴보겠습니다.

 

 

합성함수의 특성을 이용해서 우리는 g 에 적용되는 인자 x 를 합성함수 f*∘*g 의 인자로 바꿀 수 있습니다.

따라서 위 함수를 다음과 같이 변경할 수 있습니다.

 

ghci> map (\xs -> (negate . sum . tail) xs) [[1..5],[3..6],[1..7]] 

 

여기에 eta conversion 을 사용하면 람다함수를 제거할 수 있습니다.

이를 통해 pointless style 로 변경할 수 있습니다.

 

ghci> map (negate . sum . tail) [[1..5],[3..6],[1..7]] 

 

💡 (참고) point free style 이란?

암묵적 프로그래밍 (Tacit programming) 으로 불리는 이 방식은

함수 정의가 인수를 식별하지 않도록 하는 적절한 추상화를 지원하도록 합니다.

이를 통해 변환에 사용되는 인자 대신에 변환 그 자체에 좀 더 집중할 수 있습니다.

또한 등식 추론 을 자연스럽게 만드는 구조화된 조합 스타일을 강요한다는 장점도 있습니다.

 

sum lst = foldr (+) 0 lst

sum = foldr (+) 0

 

Pointfree

Pointfree - HaskellWiki

 

⚠️ 유의할 점

다만 합성함수를 사용할 때 각각의 함수가 복잡해지고 체이닝이 길어질수록

이 함수가 어떤 의도에 의해 이렇게 길어진건지 맥락 파악이 힘들어질 수 있습니다.

이때는 let binding 을 이용하면 의미있는 더 작은 단위의 레이블링된 함수로 쪼갤 수 있습니다.

 

oddSquareSum =   
    let oddSquares = filter odd $ map (^2) [1..]  
        belowLimit = takeWhile (<10000) oddSquares  
    in  sum belowLimit

 

📌 참고자료

Higher Order Functions - Learn You a Haskell for Great Good!

Anonymous function

eta conversion - Wiktionary