티스토리 뷰

6. 고차(원)함수(Higher order functions)



Haskell의 함수는 함수를 인자로 받아서, 그 return값으로 함수를 돌려줄 수 있어. 이런 식으로 함수를 인자로 받거나 돌려주거나 하는 애들을 고차(원)함수(higher order function)라고 불러. 고차(원)함수(higher order function)는 단순히 Haskell의 일부가 아니라, 거의 Haskell의 모든 것이라고 할 수 있어. 어떤 연산을 특정 상태의 변화 과정을 정의하고 그걸 반복하면서 처리하는 걸로 만드는 대신에, 그 연산 자체가 '무엇인지'를 정의하는 식으로 연산하려고 한다면, 고차(원)함수(higher order function)는 필수적인 요소가 될 거야. 이건 프로그램에 대해 생각하고 문제를 해결하는 데 있어서 굉장히 강력한 방법이야.


하스켈 커리가 만든 함수(Curried Functions)

Haskell에 있는 모든 함수들은 공식적으로 단 하나의 인자만을 받아. 그럼 우리는 여태껏 어떻게 하나 이상의 인자를 받는 다양한 함수들을 정의하고 사용할 수 있었을까? 음, 여긴 정말 영리한 기술이 들어가 있어! 지금까지 본 여러 개의 인자를 수용하는 모든 함수들은 커리 함수였어. 이게 무슨 뜻일까? 이건 예를 들어서 설명하는 게 가장 이해하기 편할거야. 우리의 좋은 친구인 max 함수를 예로 들어 보자. 이건 두 개의 인자를 받아서 그 중 더 큰 걸 돌려주는 것처럼 보여. max 4 5를 수행하는 건 첫번째로, 하나의 인자를 받아서 그 수와 4를 비교해 더 큰 숫자를 돌려주는 함수를 만들어. 그리고 5가 이 함수에 적용돼서, 우리가 원하는 결과를 만들어내지. 좀 어려워 보이는 말이지만 실제로 이건 정말 멋진 개념이야. 아래의 두 방식의 함수 호출은 완전히 동일해.

  1. ghci> max 4 5  
  2. 5  
  3. ghci> (max 45  
  4. 5  

 두 개체 사이에 공백을 놓는 건 함수적용(function application)이야. 공백은 연산의 일종처럼 동작하고 가장 높은 우선순위를 갖고 있지. max의 형(型)에 대해 한 번 설명해보자. max의 형(型) 서명은 max :: (Ord a) => a -> a -> a야. 이건 max :: (Ord a) => a -> (a -> a) 로 쓸 수도 있지. 이건 이렇게 읽을 수 있어. max는 a를 인자로 받아서 a를 인자로 받아 a를 돌려주는 함수를 돌려줘(결과값을 돌려주는 것의 기호는 ->로 표기되지). 그래서 돌려주는 형(型)과 함수의 인자가 전부 화살표를 이용해서 분리가 되는 거야.

 그래서 이런 개념이 어떤 면에서 도움이 될까? 간단히 말하자면, 우리가 함수를 적은 숫자의 인자를 통해 호출했을 때, 우리는 부분 적용된(partially applied) 함수를 얻을 수 있다는 거야. 부분 적용을 이용하면(함수를 원래 인자 개수보다 적은 개수의 인자를 이용해 호출하는 것)은 그때그때 대충 봐가면서 함수를 만들 수 있는 깔끔한 방법이고, 이걸 다른 함수에 넘기거나 몇몇 데이터들과 함께 쓸 수 있지.

 심각할 정도로 단순한 함수 하나를 보자.

  1. multThree :: (Num a) => a -> a -> a -> a  
  2. multThree x y z = x * y * z  

 multThree 3 5 9 또는 ((multThree 3) 5) 9를 호출했을 때 실제로는 어떤 일이 일어날까? 처음으로, 3이 multThree에 적용돼. 왜냐하면 얘네들은 공백을 이용해서 분리되어있기 때문이지. 이건 하나의 인자를 받아서 함수를 돌려주는 함수를 만들어. 그리고나서 5가 여기에 적용이 되고, 이건 하나의 인자를 받아서 그것과 15를 곱한 값을 돌려주는 함수를 만들어내지. 9는 이 함수에 적용이 돼서 결과값으로 135를 돌려주겠지. 이 함수의 형(型)을 multThree :: (Num a) => a -> ( a -> ( a -> a))로도 쓸 수 있다는 걸 잊지 마. 어떤 -> 앞의 개체는 -> 뒤의 것들을 돌려주는 함수의 인자를 뜻해. 따라서 이 함수는 a를 인자로 받아서 (Num a) => a -> (a -> a) 형(型)함수를 돌려주는 함수라고 볼 수 있지. 돌려주는 함수는 이와 비슷하게, a를 인자로 받아서 (Num a) => a -> a 형(型)의 함수를 돌려주는 함수가 된다. 그리고 이 함수는, 최종적으로 간단하게 a를 취해서 a를 돌려주는 함수가 되지. 아래 명령문을 봐주세요.

  1. ghci> let multTwoWithNine = multThree 9  
  2. ghci> multTwoWithNine 2 3  
  3. 54  
  4. ghci> let multWithEighteen = multTwoWithNine 2  
  5. ghci> multWithEighteen 10  
  6. 180  

 함수를 적은 개수의 인자로 호출함으로써, 말 그대로 우리는 새로운 함수를 적당히 만들어냈어. 어떤 값을 받아서 그 값과 100을 비교하는 함수를 만들고 싶다면 어떻게 해야 할까? 이런 식으로 할 수 있겠지.

  1. compareWithHundred :: (Num a, Ord a) => a -> Ordering  
  2. compareWithHundred x = compare 100 x  

 이 함수를 99를 이용해서 호출하면, 이건 GT를 돌려줄 거야. 간단하지. x가 두 식 모두에서 오른쪽 항이라는 걸 주의 깊게 봐. 이제 compare 100이 뭘 돌려줄 지 생각해보자. 이건 인자를 하나 받아서 그것과 100을 비교하는 함수를 돌려주겠지. 와! 이게 우리가 원하던 그 함수 아냐? 이걸 이렇게 다시 쓸 수 있어.

  1. compareWithHundred :: (Num a, Ord a) => a -> Ordering  
  2. compareWithHundred = compare 100  

 형(型) 서명은 그대로야. 왜냐하면 (compare 100)은 함수를 돌려주기 때문이지. compare 함수는 (Ord a) => a -> (a -> Ordering)이라는 형(型)을 갖고 있고, 100과 함께 호출한 경우 이건 (Num a, Ord a) => a -> Ordering 형(型) 서명을 가진 함수를 돌려주지. 추가된 클래스 제약조건은 100이 Num 형(型) 클래스의 일부기 때문에 은근슬쩍 붙은 거야.


 어이! 커리 함수와 부분 적용에 대해 얼마나 확실히 이해했는지 짚고 넘어가. 이건 정말 중요한 부분이야!


 중위 함수 역시 분해(section)를 통해서 부분 적용을 할 수 있어. 중위 함수를 분해하기 위해서, 단순히 이걸 소괄호로 감싼 다음에 한쪽에만 인자를 적용해주면 돼. 이건 인자를 하나 받아서 연산에서 빠진 편의 인자를 적용해주는 함수를 만들어내. 무례할만큼 하찮은 함수를 하나 보자.

  1. divideByTen :: (Floating a) => a -> a  
  2. divideByTen = (/10)  

 divideByTen 200을 호출하는 건 200 / 10, 또는 (/10) 200을 수행하는 것과 똑같아. 어떤 문자가 대문자인지 확인하는 함수를 만들어 보자.

  1. isUpperAlphanum :: Char -> Bool  
  2. isUpperAlphanum = (`elem` ['A'..'Z'])  

 분해에 관해 특별한 건 -를 쓰는 부분이야. 분해의 정의에 의해, (-4)는 어떤 숫자를 취해 그 숫자로부터 4를 빼서 돌려주는 함수가 되야해. 하지만, 편의성 때문에 (-4)는 음수 4를 의미해. 따라서 숫자를 인자로 받아서 그 수로부터 4를 빼는 함수를 만들고 싶다면, subtract 함수를 (subtract 4)와 같은 방식으로 부분적용 해야 돼.

 우리가 multThree 3 4를 GHCI에서 let 절을 이용해 어떤 이름과 묶거나 다른 함수에 넘겨주지 않고, 바로 호출을 하려고 시도하면 어떤 결과가 나타날까?

 GHCI는 해당 표현식이 a->a 형(型)의 함수를 만들어내지만 이걸 어떻게 화면에 표시해야할 지 모르겠다고 말하고 있어. 함수는 Show 형(型) 클래스의 개체가 아니고, 따라서 우리는 함수를 깔끔하게 문자열로 나타내는 방법을 얻을 수 없어. GHCI에서 1+1을 호출한다면, 이건 먼저 1+1로부터 2를 계산하고, 그 결과의 문자 표현을 얻기 위해 2에 대한 show 함수를 호출해. 그리고 2의 문자 표현은 단순히 문자열 "2"고, 이게 우리 화면에 출력되는 거지.


적절한 몇몇 고차(원)함수(higher order function)


 함수는 한숨를 인자로도 받을 수 있고 돌려줄 수도 있어. 이걸 설명하기 위해서, 함수를 하나 받아서 그 걸 두 번 적용하는 함수를 만들어볼거야!

  1. applyTwice :: (a -> a) -> a -> a  
  2. applyTwice f x = f (f x)  

 제일 먼저, 형(型) 서명을 봐. 일단 ->는 기본적으로 우측 결합이기 때문에 소괄호를 안 써도 된다는 점을 짚고 넘어가자. 하지만, 이 경우에는 꼭 소괄호를 써야해. 여기서 소괄호는 함수의 첫번째 인자가 어떤 걸 받아서 그거랑 똑같은 형(型)의 무언가를 돌려주는 함수라는 걸 가르쳐주거든. 두번째 인자는 해당 함수가 취하는 형(型)과 동일한 형(型)의 어떤 인자이고, 마지막은 applyTwice가 그거랑 같은 형(型)의 뭔가를 돌려준다는 의미지. 우린 이걸 커리 방식(curried way)으로 읽을 수 있지만, 그건 굉장히 머리가 아프니 그냥 이걸 두 개의 인자를 받아서 하나의 값을 돌려주는 함수라고 말하자. 첫번째 인자는 a->a 형(型)의 함수이고 두 번째 인자는 이거랑 같은 a야. 이 함수는 Int->Int가 될 수도 있고 String->String이 될 수도 있고 다른 어떤 것도 가능해. 하지만, 두 번째 인자는 반드시 그 형(型)과 동일한 형(型)이어야 해.


 : 이제부터, 우린 함수가 실제로는 최종적인 값을 반환하기 전까진 하나의 인자만 받아서 그게 부분 적용된 함수를 돌려준다고 말하는 대신에, 그냥 여러 개의 인자를 취한다고 이야기 할 거야. 그 내부에서 무슨 일이 일어나고 있는지 우리가 알고 있긴 하지만, 간단하게 표현하기 위해서 a->a->a가 두 개의 인자를 취한다는 식으로 이야기하는 거지.


 함수의 본체는 정말 단순해. 우린 단지 인자 f를 함수로 받아서, 그걸 공백을 이용해 분리함으로써 x에 한 번 적용시키고, 다시 그 결과에 한 번 더 f를 적용시키지. 어쨌든, 이 함수를 한 번 갖고 놀아보자.

  1. ghci> applyTwice (+310  
  2. 16  
  3. ghci> applyTwice (++ " HAHA""HEY"  
  4. "HEY HAHA HAHA"  
  5. ghci> applyTwice ("HAHA " ++) "HEY"  
  6. "HAHA HAHA HEY"  
  7. ghci> applyTwice (multThree 2 29  
  8. 144  
  9. ghci> applyTwice (3:) [1]  
  10. [3,3,1]  

 함수의 부분적용이 얼마나 놀랍고 유용한지가 증명됐어. 어떤 함수를 인자로 넘기고 싶은데 그게 단 하나의 인자만 갖는 함수를 넘겨받는다면, 그냥 부분적용을 이용해 하나의 인자만 받는 함수로 만든 다음 넘겨버리면 돼.

 이제 표준 자료실(library)에 있는 아주 유용한 함수를 고차(원)함수(higher order function)를 이용해 구현해볼거야. 이 함수는 zipWith 이라고 불려. 이건 함수와 두 개의 목록(list)을 인자로 받아서, 그 두 개 목록(list) 각각의 요소에 대해 해당 함수를 적용시켜서 두 목록(list)을 하나로 묶어주는 역할을 해. 이걸 어떻게 구현하는 지 한 번 보자.

  1. zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]  
  2. zipWith' _ [] _ = []  
  3. zipWith' _ _ [] = []  
  4. zipWith' f (x:xs) (y:ys) = f x y : zipWith' f xs ys  

형(型) 서명을 봐. 첫번째 인자는 두 개의 인자를 받아서 어떤 것을 돌려주는 함수야. 이 세 개의 형(型)은 꼭 같을 필요는 없지만, 같아도 상관없어. 두 번째 인자와 세 번째 인자는 목록(list)이야. 그 결과 역시 목록(list)이지. 첫번째 목록(list)은 a의 목록(list)이고, 왜냐하면 두 목록(list)을 합치는 함수가 a를 첫번째 인자로 받기 때문이지. 마찬가지 이유로 두 번째 목록(list)은 b의 목록(list)이야. 그리고 그 결과는 c의 목록(list)이야. 만약 함수의 형(型) 서명이 a->b->c 함수를 인자로받는 다고 말한다면, 이건 a->a->a 함수도 인자로 받아들일 수 있어. 하지만, 그 반대는 안 돼. 함수를 만들 때, 특히 고차(원)함수(higher order function)를 만들 때는, 형(型)에 대해 확신할 수 없다면 그냥 형(型) 서명을 빼먹고 :t를 이용한 Haskell의 추론으로 그게 어떤 형(型)인지 확인해볼 수 있다는 걸 기억해.

 이 함수의 동작은 일반적인 zip과 정말 비슷해. 경계조건은 동일하고, 다른 점은 둘을 하나로 합치는 함수가 인자로 추가됐다는 것 밖에 없어. 하지만 이 인자는 경계조건에 영향을 미치지 않고, 그래서 여기선 _을 이용했지. 그리고 마지막 패턴에서 함수의 본체는 zip과 비슷해. 단지 이건 (x,y)로 만드는 작업을 하는 대신에, f x y를 적용한다는 점이 다르지. 하나의 고차(원)함수(higher order function)는 그게 충분히 일반적이라면 다양한 종류의 문제에서 이용될 수 있어. 여기 zipWith 함수가 할 수 있는 다양한 일들에 대한 작은 증거이 있어.

  1. ghci> zipWith' (+) [4,2,5,6] [2,6,2,3]  
  2. [6,8,7,9]  
  3. ghci> zipWith' max [6,3,2,1] [7,3,1,5]  
  4. [7,3,2,5]  
  5. ghci> zipWith' (++) ["foo ""bar ""baz "] ["fighters""hoppers""aldrin"]  
  6. ["foo fighters","bar hoppers","baz aldrin"]  
  7. ghci> zipWith' (*) (replicate 5 2) [1..]  
  8. [2,4,6,8,10]  
  9. ghci> zipWith' (zipWith' (*)) [[1,2,3],[3,5,6],[2,3,4]] [[3,2,2],[3,4,5],[5,4,3]]  
  10. [[3,4,6],[9,20,30],[10,12,12]]  

 봤듯이, 하나의 고차(원)함수(higher order function)가 정말 다재다능한 방식으로 쓰이고 있지. 명령형 언어에서는 어떤 행동을 하기 위해 for 루프, while 루프, 어떤 변수에 값을 대입하는 것, 그 상태를 검사하는 것 등등의 과정이 많이 이용되고, 그걸 함수처럼 인터페이스로 감싸지. 함수형 언어에서는 두 개의 목록(list)을 하나의 페어로 만들고 그걸로 뭔가를 하거나 해의 집합을 얻어서 그 중 내가 필요 없는 것들을 제거하는 등 일반적인 패턴을 추상화하기 위해서 고차(원)함수(higher order function)를 이용해.

 이번엔 flip이라고 불리는 표준자료실(library)의 함수를 한 번 구현해 볼거야. flip은 단순히 함수를 하나 취해서, 원래의 함수와 유사하지만 첫 두 개의 인자 순서가 뒤집힌 함수를 반환해. 우린 이걸 이런 방식으로 구현할 수 있어.

  1. flip' :: (a -> b -> c) -> (b -> a -> c)  
  2. flip' f = g  
  3.     where g x y = f y x  

 형(型) 서명을 읽어봐. 이건 a와 b를 인자로 취하는 함수를 인자로 받아서 b와 a를 인자로 취하는 함수를 돌려주고 있어. 하지만 함수는 기본적으로 커리되기(curried) 때문에, 두 번째의 소괄호 쌍은 실제로는 아무 의미없어(-> 함수는 기본적으로 우측 결합이니까). (a->b->c)->(b->a->c)는 (a->b->c) ->(b->(a->c))하고 똑같고, 이건 (a->b->c)->b->a->c하고도 똑같아. 우리는 g x y = f y x라고 썼지. 그게 성립한다면, f y x = g x y라고 쓰는 것도 당연히 가능해야 겠지? 이걸 기억해둬, 우린 더 간단한 방식으로 이 함수를 정의할 수 있어.

 여기서 함수가 커리된다(curried)는 사실로부터 얻을 수 있는 이득이 있어. flip' f를 인자 y와 x없이 호출했을 때, 이건 두 인자의 호출 순서만 뒤바뀐 함수 f를 돌려줘. 뒤집힌 함수가 종종 다른 함수의 인자로 넘겨진다고 해도, 미리 생각해서 모든게 적용됐을 때 함수의 결과가 어떻게 될지 작성함으로써, 고차(원)함수(higher order function)를 만들 때 커링의 이익을 얻을 수 있어.

  1. ghci> flip' zip [1,2,3,4,5"hello"  
  2. [('h',1),('e',2),('l',3),('l',4),('o',5)]  
  3. ghci> zipWith (flip' div) [2,2..] [10,8,6,4,2]  
  4. [5,4,3,2,1]  


map과 filter


 map은 함수와 목록(list)을 인자로 받아서 해당 목록(list)의 모든 원소에 그 함수를 적용시켜서, 새로운 목록(list)을 만들어 내. 이거 형(型) 서명이 뭔지, 이게 정의하는 게 뭔지 봐봐.

  1. map :: (a -> b) -> [a] -> [b]  
  2. map _ [] = []  
  3. map f (x:xs) = f x : map f xs  

 형(型) 서명은 이 함수가 a를 인자로 취해서 b를 돌려주는 함수와, a의 목록(list)을 인자로 받아서 b의 목록(list)을 돌려준다고 말하고 있어. 함수의 형(型) 서명만 봐도 가끔씩 그 함수가 하는 일이 뭔지 알 수 있다는게 참 흥미롭지. map은 굉장히 다양한 방법으로 이용될 수 있는 다재다능한 고차(원)함수(higher order function)야. 동작 예제를 몇 가지 살펴보자.

  1. ghci> map (+3) [1,5,3,1,6]  
  2. [4,8,6,4,9]  
  3. ghci> map (++ "!") ["BIFF""BANG""POW"]  
  4. ["BIFF!","BANG!","POW!"]  
  5. ghci> map (replicate 3) [3..6]  
  6. [[3,3,3],[4,4,4],[5,5,5],[6,6,6]]  
  7. ghci> map (map (^2)) [[1,2],[3,4,5,6],[7,8]]  
  8. [[1,4],[9,16,25,36],[49,64]]  
  9. ghci> map fst [(1,2),(3,5),(6,3),(2,6),(2,5)]  
  10. [1,3,6,2,2]  

 아마 이것들이 조건제시형 목록(list)을 통해서도 가능하다는 걸 느꼈을 거야. map (+3) [1,5,3,1,6]은 [x+3 | x  <- [1,5,3,1,6]]이라고 쓰는거랑 똑같아. 하지만, map을 쓰는게 몇몇 함수들을 목록(list)에 적용시킬 때, 특히 map의 map을 다루는 것과 같이 전체 원소들 여러 개의 대괄호에 둘러 싸여 복잡하게 되는 상황같은 때에는 훨씬 읽기 좋아.

 filter는 조건서술부(predicate)(조건서술부(predicate)는 어떤게 참인지 아닌지를 말하는 함수야. 이 경우에는 참 거짓값을 돌려주는 함수라고 봐야겠지.)와 목록(list)을 취해서 해당 조건서술부(predicate)를 만족하는 원소들로만 구성된 목록(list)을 돌려주는 함수야. 형(型) 서명과 구현은 다음과 같아.

  1. filter :: (a -> Bool) -> [a] -> [a]  
  2. filter _ [] = []  
  3. filter p (x:xs)   
  4.     | p x       = x : filter p xs  
  5.     | otherwise = filter p xs  

 정말 간단하지. p x가 True로 평가되면, 원소는 새로운 목록(list)에 포함이 돼. 그렇지 않다면 포함되지 못할거고. 몇가지 사용예제를 살펴보자.

  1. ghci> filter (>3) [1,5,3,2,1,6,4,3,2,1]  
  2. [5,6,4]  
  3. ghci> filter (==3) [1,2,3,4,5]  
  4. [3]  
  5. ghci> filter even [1..10]  
  6. [2,4,6,8,10]  
  7. ghci> let notNull x = not (null x) in filter notNull [[1,2,3],[],[3,4,5],[2,2],[],[],[]]  
  8. [[1,2,3],[3,4,5],[2,2]]  
  9. ghci> filter (`elem` ['a'..'z']) "u LaUgH aT mE BeCaUsE I aM diFfeRent"  
  10. "uagameasadifeent"  
  11. ghci> filter (`elem` ['A'..'Z']) "i lauGh At You BecAuse u r aLL the Same"  
  12. "GAYBALLS"  

 이것들은 전부 조건서술부(predicate)를 이용한 조건형 목록(list)으로 만들 수 있는 것들이야. map과 filter, 조건형 목록(list)을 사용하는 상황이 뭔지 딱 정해진 규칙같은 건 없지만, 그냥 명령문(code)과 문맥에 따라서 뭐가 더 읽기가 좋은지 적절히 선택해서 이용하면 돼. 조건형 목록(list)에서 여러 개의 조건서술부(predicate)를 적용하는 것과 같이 filter를 쓰고 싶다면, filter 함수를 여러번 적용하거나, 조건서술부(predicate)를 논리 &&함수를 이용해서 결합해 사용하면 돼.

이전 장에서 빠른 정렬(quick sort) 함수 구현했던 거 생각나? 우린 그 때 목록(list)의 원소들을 피벗보다 작거나 같은 것과 큰 것들로 분리하기 위해 조건형 목록(list)을 썼어. 이걸 filter를 이용해서 함수적으로 똑같지만 더 읽기좋게 쓸 수 있어.

  1. quicksort :: (Ord a) => [a] -> [a]    
  2. quicksort [] = []    
  3. quicksort (x:xs) =     
  4.     let smallerSorted = quicksort (filter (<=x) xs)  
  5.         biggerSorted = quicksort (filter (>x) xs)   
  6.     in  smallerSorted ++ [x] ++ biggerSorted  

 map과 filter를 쓰는 건 모든 함수형 프로그래머에게 있어 밥줄같은 거야. 아, 조건형 목록(list)을 쓸지 map과 filter 함수를 써서 풀지 같은 건 별 문제가 아냐. 특정 둘레를 가진 직각 삼각형을 어떻게 찾는지 구하는 문제를 어떻게 풀지로 돌아가보자. 명령형 언어에서, 이건 세 개의 중첩 반복문, 그리고 그 내부에서 현재 조합이 직각 삼각형인지, 둘레가 맞는지를 확인하는 조건문을 이용해서 풀어야해. 그리고 조건을 만족하면 그 내용을 화면에 띄우거나 그걸로 뭔가를 하겠지. 함수형 언어에서는, 이런 패턴은 보통 map과 filter를 이용해서 해결해. 어떤 값을 취해서 특정 결과를 만들어내는 함수를 만들고, 그 함수와 값의 목록(list)을 map하고, 그 다음 그 결과 리스 중 우리가 찾고 있는 조건을 만족하는 원소들을 filter하는거지. Haskell의 게으름 덕분에, 목록(list) 전체를 여러번 map하고 또 여러번 filter한다해도, list자체는 단 한 번만 넘겨져.

 100,000보다 작은 숫자 중에서 3829로 나눠지는 가장 큰 숫자를 찾아보자. 이걸 하기 위해서, 단순히 그 해를 만족하는 가능성이 있는 집합을 filter하기만 하면 돼.

  1. largestDivisible :: (Integral a) => a  
  2. largestDivisible = head (filter p [100000,99999..])  
  3.     where p x = `mod` 3829 == 0  

 먼저 100,000보다 작은 모든 수의 목록(list)을 100,000부터 시작해서 감소하게 만들었어. 그리고 이걸 조건서술부(predicate)를 이용해서 filter했고, 목록(list)이 100,000부터 내림차순으로 정렬되어있기 때문에, 우리 조건서술부(predicate)를 만족하는 가장 큰 숫자는 filter된 목록(list)의 제일 첫번째 원소가 되겠지. Haskell의 게으른 동작 덕분에 시작 집합을 유한 집합으로 할 필요도 없어. filter한 목록(list)의 head만 사용하는 걸로 끝나기 때문에, filter된 목록(list)이 유한인지 무한인지 같은 것도 전혀 신경쓸 필요없지. 평가는 첫번째로 조건을 만족하는 해를 찾았을 때 중단돼.

 다음으로는, 10,000보다 작은 모든 홀수 제곱수들의 합을 구해볼거야. 하지만 먼저, 이 답을 구하기 위해 takeWhile 함수에 대해 소개해야할 필요가 있어. 이건 조건서술부(predicate)와 목록(list)을 인자로 받아서, 목록(list)의 시작부터 조건서술부(predicate)가 거짓이 될 때까지 원소들로 이루어진 목록(list)을 반환해. 만약 "elephants know how to party."라는 문자열에서 첫 번째 단어를 얻고 싶다면, takeWhile (/=' ') "elephants know how to party."라고 쓰면 돼. 그러면 "elephants"라는 결과가 나올 거야. 좋아. 10,000보다 작은 모든 홀수 제곱수들의 합을 구해보자. 먼저, (^2)함수를 무한 목록(list) [1...]과 관계설정(mapping)할거야. 그리고 이 중 홀수만 얻을 수 있게 filter하면 되겠지. 그 다음으로, 목록(list)의 모든 원소들을 걔네들이 10,000보다 작을 때까지만 취하면 돼. 최종적으로, 그 목록(list)의 합을 구하면 되겠지. 이걸 위한 함수도 따로 정의할 필요없이, 그냥 GHCI에서 한 줄로 구현할 수 있어.

  1. ghci> sum (takeWhile (<10000) (filter odd (map (^2) [1..])))  
  2. 166650  

 멋지군! 초기 데이터(모든 자연수의 무한 목록(list))로부터 시작해서, 거기에 map을 쓰고, filter하고 우리의 조건을 만족하는 범위에서 잘라내고 그 전체를 합했어. 이것도 역시 조건목록(list)을 이용해서 표현가능해.

  1. ghci> sum (takeWhile (<10000) [n^2 | n <- [1..], odd (n^2)])  
  2. 166650  

 이건 그냥 어떤게 더 아름답다고 생각하는지에 따른 취향의 문제야. 다시 한 번 말하지만, Haskell의 게으른 특성이 이걸 가능하게 만들어. 무한대의 목록(list)에 map과 filter를 사용하면, 이건 그 순간 바로 해당 목록(list)에 map과 filter를 적용하는게 아니라, 해당 동작의 수행을 뒤로 미뤄. Haskell에게 sum 함수를 이용해서 결과를 달라고 요구했을 때에만, 동작을 수행해. sum은 다시 takeWhile에게 결과를 요청하고, takeWhile은 필터링(filtering)과 관계설정(mapping)이 일어나게 만들지. 하지만 takeWhile의 조건서술부(predicate) 때문에 10,000이하의 수까지만 적용돼.

 다음 문제로 넘어가서, 이번엔 콜라츠 수열에 대해 다뤄볼거야. 이건 하나의 자연수를 취해서, 그게 짝수이면 그걸 2로 나눠. 만약 홀수라면, 3을 곱해서 1을 더해줘. 그리고 그 결과값을 이용해서 다시 똑같은 과정을 반복해. 요약하자면, 이 과정을 통해 일련의 숫자를 얻게 돼. 그리고 모든 시작 숫자에 대해서, 이 숫자배열은 결국 숫자 1로 끝나게 되는 걸로 추측하고 있어. 예를 들어서 13을 시작 숫자로 삼으면, 이런 숫자 배열을 얻을 수 있지. 13, 40, 20, 10, 5, 16, 8, 4, 2, 1. 13*3 +1은 40과 같고, 40은 2로 나누면 20이고, 그런 식으로 쭉 연산하는 거야. 이 숫자 배열은 길이가 10이야.

 이제 진짜 알고 싶은 건 이거야. 1부터 100사이의 모든 시작 숫자에 대해서, 얼마나 많은 숫자 배열이 15보다 긴 길이를 갖고 있는가? 먼저, 해당 숫자열을 만들어내는 함수를 한 번 만들어보자.

  1. chain :: (Integral a) => a -> [a]  
  2. chain 1 = [1]  
  3. chain n  
  4.     | even n =  n:chain (n `div` 2)  
  5.     | odd n  =  n:chain (n*3 + 1)  

 모든 배열은 1로 끝나기 때문에, 이게 경계조건이야. 이건 정말 전형적인 재귀함수지.

  1. ghci> chain 10  
  2. [10,5,16,8,4,2,1]  
  3. ghci> chain 1  
  4. [1]  
  5. ghci> chain 30  
  6. [30,15,46,23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1]  

 좋아! 이건 정상적으로 동작하는 것 같아. 그리고, 이제 아까 질문에 대한 대답을 알려줄 함수를 만들어보자.

  1. numLongChains :: Int  
  2. numLongChains = length (filter isLong (map chain [1..100]))  
  3.     where isLong xs = length xs > 15  

 모든 목록(list)으로 표현되는 각 숫자배열들의 목록(list)을 얻기 위해 [1..100]목록(list)과 chain 함수를 관계설정(mapping)시켰어. 그리고, 해당 숫자배열의 길이가 15보다 큰지 확인하는 조건서술부(predicate)를 이용해 이것들을 필터링했지. 필터링을 한 다음에는, 얼마나 많은 숫자배열들이 결과 목록(list) 안에 남아있는지 개수만 확인하면 돼.


 : 이 함수는 numLongChains :: Int 형(型)을 갖고 있어. 왜냐하면 length 함수는 역사적인 이유때문에 Num a 대신에 Int 형(型)을 반환하거든. 만약 이 값을 좀 더 일반적인 Num a로 사용하고 싶다면, 결과 길이값에 fromIntegral 함수를 이용해야 돼.


 map을 사용해서, 커링이 어떻게 동작하는지, (부분 적용된)함수가 어째서 다른 함수의 인자가 될 수 있거나 혹은 목록(list)의 원소가 될 수 있는 실제 값인지(단지 문자열로 바꿀 수 없을 뿐) 설명하는 것말고 다른 이유가 없다면, map (*) [0..]과 같은 것도 할 수 있어. 지금까지는 목록(list)의 원소에 대해 하나의 인자를 취하는 함수만 관계설정(mapping)해왔어. (num a)=> [a] 형(型)의 목록(list)를 얻기 위해 map (*2) [0..]를 쓰는 것같이 말이야. 하지만 map (*) [0..]같은 것도 아무 문제 없이 쓸 수 있어. 이 때 일어나는 일은, 해당 목록(list)에 있는 값들에 (Num a)=> a->a->a 형(型)을 가진 * 함수가 적용된다는 거야. 두 개의 인자를 가진 함수에 하나의 인자를 적용시키면 하나의 인자를 취하는 함수를 돌려주지. 만약 * 함수를 [0..]목록(list)에 적용시킨다면, 그 결과는 하나의 인자를 취하는 함수들의 목록(list)이 될거야. 따라서 그 목록(list)의 형(型)은 (Num a) => [a->a]가 되겠지. map (*) [0..]은 [(0*),(1*),(2*),(3*),(4*),(5*)..]라고 씀으로써 얻을 수 있는 목록(list)과  비슷한 걸 생성해.

  1. ghci> let listOfFuns = map (*) [0..]  
  2. ghci> (listOfFuns !! 45  
  3. 20  

 이 목록(list)에서 네 번째 인덱스의 원소를 가져오는 건, (4*)와 동일한 함수를 돌려줘. 그리고 여기에 5를 적용하면 (4*) 5 또는 4 * 5라고 쓰는 것과 동일하겠지.


람다(Lambdas)


 람다는 기본적으로 딱 한 번만 쓰기 위해 필요한 익명 함수(anonymous functions)야. 보통, 고차(원)함수(higher order function)에 한 번 넘길 목적으로 람다를 만들어서 써. 람다를 만들기 위해, \ 기호를 쓰고(이게 잘 보면 그리스 문자 람다랑 비슷하게 보이기 때문에 그래 *역주: 백슬래쉬 말하는 겁니다. 한글 글꼴에서는 원화기호라 잘 와닿지 않음.) 그 뒤에 공백으로 분리된 인자를 써. 그 다음에는 ->와 함수의 본체가 오지. 보통 이걸 소괄호로 감싸는데, 그렇게 하지 않으면 이건 항상 오른쪽으로 확장되기 때문이야.

 15 cm정도만 위쪽을 봐봐. 아마 numLongChains 함수에서 isLong 함수를 filter에 넘기기 위한 목적으로 where 절을 쓴게 보일거야. 이럴 때, 대신에 람다를 이용할 수 있어.

  1. numLongChains :: Int  
  2. numLongChains = length (filter (\xs -> length xs > 15) (map chain [1..100]))  

 람다는 표현식이기 때문에, 위와 같은 방식으로 넘길 수 있어. (\xs -> length xs > 15)는 인자로 넘어온 목록(list)의 길이가 15보다 큰 지 아닌지 판단하는 함수를 돌려줘.

 커링이 어떻게 동작하는지, 그리고 함수의 부분 적용이 어떻게 동작하는지 잘 숙지하지 못한 사람들은 종종 람다를 쓸 필요가 없는 곳에서 람다를 써. 예를 들어서, 표현식 map (+3) [1,6,3,2]와 map (\x-> x + 3) [1,6,3,2] 는 (+3)과 (\x -> x +3)이 모두 숫자를 취해서 거기 3을 더해 돌려주는 동일한 함수를 돌려주기 때문에 완전히 똑같아. 굳이 말할 필요도 없겠지만, 이 경우에는 함수의 부분 적용이 훨씬 읽기좋기 때문에 람다를 쓰는 건 멍청한 짓이야.

 일반적인 함수처럼, 람다도 여러 개의 인자를 받을 수 있어.

  1. ghci> zipWith (\a b -> (a * 30 + 3) / b) [5,4,3,2,1] [1,2,3,4,5]  
  2. [153.0,61.5,31.0,15.75,6.6]  

 그리고 또 일반적인 함수처럼, 람다에서도 패턴 매칭을 사용할 수 있어. 한 인자에 대해 여러 개의 패턴을 정의할 수 없다는 게 유일한 차이점이야. 람다에서는 하나의 동일한 인자에 대해 []인 경우, (x:xs)인 경우 등의 여러 개의 패턴을 만들수는 없어. 만약 람다에서 패턴 매칭이 실패할 경우에는,런타임 오류(error)를 발생시켜. 그래서 람다에서 패턴 매칭을 사용할 땐 좀 신중해질 필요가 있지!

  1. ghci> map (\(a,b) -> a + b) [(1,2),(3,5),(6,3),(2,6),(2,5)]  
  2. [3,8,9,8,7]  

 오른쪽으로 전부 확장 가능하다는 의미를 갖게 하고 싶을 때가 아니면 보통 소괄호로 람다를 감싸. 좀 흥미로운 게 있어. 함수는 기본적으로 커리될 수 있기 때문에, 아래의 두 가지는 동일해. 

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


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

 만약 함수를 이런식으로 정의한다면, 이것들의 형(型) 서명이 왜 이렇게 되는 지가 명백해져. 세 개의 ->가 형(型) 서명과 등식 모두에 존재해. 물론, 첫 번째 방식으로 함수를 정의하는게 훨씬 읽기 좋고, 두 번째 방식은 그냥 커링을 설명하기 위한 기믹에 가깝지.

 하지만, 이런 방식의 표기가 더 멋진 경우가 있어. flip 함수의 경우엔 이런 식으로 정의하는 게 가장 읽기 좋다고 생각해.

  1. flip' :: (a -> b -> c) -> b -> a -> c  
  2. flip' f = \x y -> f y x  

 이건 flip' f x y = f y x라고 쓰는 거랑 똑같지만, 이렇게 쓰면 이 함수가 대부분의 경우 새로운 함수를 만드는 것에 쓰일 거라고 명확하게 말할 수 있어. flip을 쓰는 가장 일반적인 경우는 이걸 함수 인자와 함께 호출해서 결과 함수르 ㄹmap이나 filter를 적용시켜서 넘기는 거거든. 따라서 이 경우에는 람다를 쓰는게 네가 함수에서 구현하고자 하는게 주로 부분 적용된 함수를 만들어서 다른 함수에 인자로 넘기고자 하는 것이라는 걸 더 명확하게 만들어 줘.


 그냥 접는 것과 말(Only folds and horses)


 재귀를 다루는 걸로 돌아가서, 대부분의 목록(list)을 다루는 재귀함수들은 일종의 형식이 있다는 걸 알고 있겠지. 얘네들은 거의 텅 빈 목록(list)에 대한 경계 조건을 갖고 있어. 그리고 목록(list)의 한 원소와 나머지 부분에 대해 어떤 동작을 하는 x:xs 패턴에 대해서도 배웠지. 이건 정말 일반적인 패턴이고, 따라서 이런 패턴을 캡슐화하고 있는 유용한 함수들을 몇 개 소개해볼거야. 이 함수들은 fold라고 불려. map 함수와 비슷한 종류의 애들이지만, 얘들은 map과는 다르게 목록(list)을  어떤 하나의 원소로 줄여버려.

 fold는 이진 함수(binary function)와 시작 값(난 이걸 누산기accumulator라고 부르는 걸 좋아해), 그리고 접을(fold up) 목록(list)을 인자로 받아. 이진 함수는 그 자체로 두 개의 인자를 취하지. 이진 함수는 누산기와 목록(list)의 첫 번째, 또는 마지막 원소를 인자로 받아서 새로운 누산기를 만들어내. 그리고, 이진 함수는 다시 한번 이 새로운 누산기와, 목록(list)의 새로운 첫번째(혹은 마지막) 원소를 받아서 계산하고, 그걸 반복하지. 전체 목록(list)에 대한 순회가 끝나면 누산기만 남게 되고, 이게 목록(list)을 줄인(reduce) 결과야.

 먼저 왼쪽 접기(left fold)라고도 불리는 foldl 함수에 대해 알아보자. 이건 목록(list)을 왼쪽 편에서부터 접어. 이진 함수는 시작 값과 목록(list)의 head로부터 적용돼. 그리고 새로운 누산기를 만들어내고, 이진 함수는 그 값과 다음 원소에 대해 적용되는 과정을 반복하지.

 sum 함수를 다시 구현해보자. 이번에는, 명확한 재귀 대신에 접기(fold)를 이용할 거야.

  1. sum' :: (Num a) => [a] -> a  
  2. sum' xs = foldl (\acc x -> acc + x) 0 xs  

 실험해보자. 하나, 둘, 셋.

  1. ghci> sum' [3,5,2,1]  
  2. 11  

 이 fold가 어떤 일을 일으키는 지 내부적인 동작을 한 번 살펴보자. \acc x -> acc +x는 이진 함수야. 0은 시작 값이고, xs는 접힐 함수를 말하지. 이제 첫번째로, 0이 이진 함수에서 acc 인자로 사용되고, 3이 x(혹은 현재 원소) 인자로 사용돼. 0+3의 결과로 3이 나올 거고, 이게 새로운 누산기 값이 되겠지. 다음으로, 3이 새로운 누산기 값으로 이용되고 5가 현재 원소가 돼서, 그 결과로 8이 새로운 누산기 값이 될거야. 다음으로 가서, 8이 누산기 값이고, 2가 현재 원소고, 새로운 누산기 값은 10이 되겠지. 마지막으로 10이 누산기 값이 되고, 1이 현재 원소가 되고, 그 결과로 11이 만들어질거야. 축하해. 넌 접기를 끝마쳤어!

 왼쪽의 프로페셔널한 그림은 접기가 어떻게 수행되는지 순서대로 잘 보여주고 있어. 연두색 숫자는 누산기 값이야. 이 그림을 통해 누산기에 의해 왼쪽 편에서부터 목록(list)이 어떻게 소비되는지를 알 수 있어. 냠냠냠냠! 커리된 함수에 대해 고려한다면, 이 구현을 좀 더 간결하게 할 수 있어. 이렇게 말야.



  1. sum' :: (Num a) => [a] -> a  
  2. sum' = foldl (+) 0  

 람다 함수 (\acc x -> acc + x)는 (+)랑 똑같아. xs를 인자로 넣을 필요도 없어. 왜냐하면 foldl (+) 0이 호출되면 이건 목록(list)을 인자로 취하는 함수를 돌려줄테니까. 일반적으로, foo a = bar b a라는 함수가 있다면 이건 foo = bar b라고도 쓸 수 있어. 커링(currying) 때문이지.

 어쨌건, 오른쪽 접기로 넘어가기 전에 왼쪽 접기로 다른 함수를 하나 더 구현해보자. elem이 어떤 값이 목록(list)에 속하는 함수인지 아마 알고 있을거고, 그래서 다시 설명하진 않을거야(이런, 벌써 설명했잖아!). 이걸 왼쪽 접기를 이용해서 구현해보자.

  1. elem' :: (Eq a) => a -> [a] -> Bool  
  2. elem' y ys = foldl (\acc x -> if x == then True else acc) False ys  

 좋아,좋아. 여기서 뭘 한거지? 시작값과 누산기가 여기서는 논리 값(boolean value)이야. fold를 쓸 때 누산기 값과 최종 결과값의 형(型)항상 같아야 돼. 어떤 걸 시작값으로 써야할지 모르겠다면, 이 말을 명심해. 최종 결과값의 형(型)을 생각하는 게 시작 값을 설정할 때 도움을 줄 거야. 여기선 시작값으로 False를 썼어. False를 시작값으로 두는 건 당연해. 일단 목록(list)에 존재하지 않을 거라고 가정하고 보는거지. 그리고, 빈 목록(list)에 대해서 fold를 호출했을 때, 그 결과는 시작값과 같아야 해. 그리고 현재 원소가 우리가 찾고 있는 원소인지 확인하는 거지. 그리고 우리가 찾는 원소가 있다면, True로 누산기 값을 설정해. 그렇지 않다면, 누산기 값을 변경하지 않고 그대로 넘기는 거야. 만약 이전게 False값이었다면, 이건 그대로 False야. 왜냐하면 현재 원소도 찾던 원소가 아니니까. 이전에 누산기가 True 였다면, 어쨌든 하나는 찾은 거니까 계속 True겠지.

 오른쪽 접기, foldr은 왼쪽 접기랑 거의 똑같이 동작해, 다만 누산기가 목록(list)의 오른쪽부터 잡아먹는다는 것을 제외하면 말야. 또, 왼쪽 접기의 이진 함수는 누산기 값을 첫번째 인자로, 현재 원소의 값을 두번째 인자로 받지만,(그래서 \acc x -> ... ), 오른쪽 접기의 이진 함수는 현재 원소의 값을 첫번째 인자로, 누산기 값을 두 번째 인자로 받아(그래서 \x acc -> ...). 오른쪽 접기가 누산기 값을 두 번째 인자로 받는 건, 이게 오른쪽 편부터 접어나가는 함수이기 때문에 당연한 거라고 봐야겠지.

 fold에서 누산기 값(그리고 결과값)은 어떤 형(型)이든 될 수 있어. 숫자도 될 수 있고, 논리 값이 될 수도 있고, 심지어는 새로운 목록(list)이 될 수도 있지. 오른쪽 접기를 이용해서 map 함수를 구현해보자. 누산기 값은 목록(list)이  될 거고, 원소 하나하나 단위로 관계설정(mapping)된 목록(list)이 차곡차곡 누적이 되겠지. 이로부터, 시작 값은 텅 빈 목록(list) 일 거라는 건 자명하게 도출되지.

  1. map' :: (a -> b) -> [a] -> [b]  
  2. map' f xs = foldr (\x acc -> f x : acc) [] xs  

만약 (+3)을 [1,2,3]에 관계설정(mapping)시킨다면, 이건 목록(list)의 오른쪽 편에서부터 시작할거야. 마지막 원소인 3을 취해서, 거기에 함수를 적용시키면, 그 값은 6이 되겠지. 그리고 이 6을 현재 누산기 값인 []의 맨 앞에 붙여. 그럼 6:[]이 될거고 이건 [6]이랑 마찬가지며, 새로운 누산기 값이 되겠지. 다음으로 (+3)을 2에 적용시키고, 그 결과인 5를 누산기 앞에 붙이겠지(: 연산을 통해). 그 결과 누산기 값은 [5,6]이 될거야. 마지막으로 (+3)함수를 1에 적용시키고, 이걸 누산기 앞에 붙이면 최종 결과는 [4,5,6]이 되겠지.

 당연히, 이 함수를 왼쪽 접기로도 구현할 수 있어. 아마 map' f xs = foldl (\acc x -> acc ++ [f x]) [] xs 형태가 되겠지. 하지만 ++ 함수가 : 함수보다 훨씬 비용이 높기 때문에, 목록(list)으로부터 새로운 목록(list)을 만들 때에는 보통 오른쪽 접기를 써.

 만약 목록(list)을 뒤집고 싶다면, 왼쪽 접기로 구현하나 오른쪽 접기로 구현하나 거기서 거기일거야. 꼭 둘 중 하나로 해야만 하는 경우가 아닐 때도 가끔 존재해. sum 함수도 왼쪽으로 접든 오른쪽으로 접든 거의 똑같이 구현할 수 있지. 하나의 큰 차이점은, 오른쪽 접기는 무한 크기의 목록(list)에 대해서 동작할 수 있는 반면, 왼쪽 접기는 그렇게 할 수 없다는 거야. 더 알기 쉽게 말하자면, 무한 목록(list)의 어떤 지점에서 시작해서 그걸 오른쪽부터 접어나가면, 결국 이건 목록(list)의 시작점에 도달하게 될거야. 하지만, 무한 목록(list)을 어떤 시점에서 시작해서 그걸 왼쪽부터 접어나가면, 이건 절대 끝에 도달할 수 없겠지!

 fold는 목록(list)을 단 한 번 원소 단위로 순회해서, 거기에 기반한 어떤 것을 돌려주는 함수를 구현하고 싶을 때 사용될 수 있어. 뭔가 결과값을 얻기 위해 어떤 목록(list)을 순회해야 하는 상황이라면, fold를 쓰고 싶은 상황에 직면한거야. 그리고 이게 바로 fold가 map, filter와 같이 쓰이며, 함수형 프로그래밍에서 가장 유용한 형(型)의 함수인 이유이지.

 foldl1과 foldr1은 foldl과 foldr하고 정말 유사해. 다만 이건 명확한 시작 값을 줄 필요가 없어. 이건 목록(list)의 첫번째(혹은 마지막) 원소가 시작값이라고 가정하고 해당 원소의 다음 원소부터 접기를 시작해. 따라서 sum 함수는 이렇게 구현할 수 있어. sum = foldl (+). 얘네들은 접을 원소가 반드시 하나 이상 존재해야하기 때문에, 텅빈 목록(list)으로 호출했을 경우에는 실행시 오류(Runtime Error)를 발생시켜. foldl과 foldr은 반면에 텅빈 목록(list)와도 잘 동작하지. fold를 만들 때, 이게 텅빈 목록(list)와 어떻게 동작할지를 잘 생각해. 만약 이 함수가 텅 빈 목록(list)이 주어졌을 때 동작하는 게 말이 안된다면, 그걸 구현하기 위해서 아마 foldl1 이나 foldr1을 쓸 수 있을 거야.

 fold가 얼마나 강력한지 확인하기 위해서, 몇개의 표준자료실(library) 함수를 fold를 이용해 구현해보자.

  1. maximum' :: (Ord a) => [a] -> a  
  2. maximum' = foldr1 (\x acc -> if x > acc then x else acc)  
  3.   
  4. reverse' :: [a] -> [a]  
  5. reverse' = foldl (\acc x -> x : acc) []  
  6.   
  7. product' :: (Num a) => [a] -> a  
  8. product' = foldr1 (*)  
  9.   
  10. filter' :: (a -> Bool) -> [a] -> [a]  
  11. filter' p = foldr (\x acc -> if p x then x : acc else acc) []  
  12.   
  13. head' :: [a] -> a  
  14. head' = foldr1 (\x _ -> x)  
  15.   
  16. last' :: [a] -> a  
  17. last' = foldl1 (\_ x -> x)  

 head는 패턴 매칭을 이용해서 구현하는 편이 낫지만, 그냥 보여주기 위해서 fold를 이용해 구현해봤어. 내 생각에는 이 reverse 함수의 정의가 정말 똑똑한 것 같애. 시작 값을 텅 빈 목록(list)으로 받아서, 목록(list)을 왼쪽부터 순회하며 그걸 누산기의 앞에 붙이지. 결과적으로, 뒤집힌 목록(list)을 얻을 수 있어. \acc x -> x : acc는 : 함수와 인자의 순서만 바뀌었을 뿐 똑같은 함수기 때문에, 이걸 foldl (flip (:)) []로도 쓸 수 있어.

 왼쪽 접기와 오른쪽 접기를 다르게 설명하면 이렇게도 말할 수 있어. 오른쪽 접기와 이진 함수 f, 그리고 시작값 z가 있다고 하자. 전체 목록(list) [3,4,5,6]에 대한 오른쪽 접기는, 본질적으로 다음과 같아. f 3(f 4(f 5(f 6 z))). f는 목록(list)의 마지막 원소와 누산기를 이용해 호출이 되고, 그 다음 누산기로 주어진 값은 마지막 다음 값과 계산되고, ... 그렇게 반복되겠지. 만약 f가 + 함수라고 하고 시작 값을 0이라고 하자. 그럼 이건 3 + (4 + ( 5 + (6 + 0)))과 같아. 혹은 + 함수를 전위 함수로 생각하면, 이건 (+) 3((+) 4 ((+) 5 ((+) 6 0 )))이랑 같겠지. 비슷하게, 목록(list)에 대해 g 이진 함수와 초기값 z를 이용해 왼쪽에서 접는 건 g (g (g ( g z 3) 4 ) 5) 6과 같아. 만약 flip (:) 함수를 이진 함수로 이용하고 []를 누산기로 이용한다면(그래서 목록(list)을 뒤집는다면), 그건 flip (:) ( flip (:) (flip (:) (flip (:) [] 3) 4) 5) 6하고 같겠지. 그리고, 그 결과는 당연히 [6,5,4,3]이 될거야.

 scanl 과 scanr은 foldl과 foldr이랑 비슷해. 다만 얘네들은 중간 과정의 누산기 상태를 전부 저장한 목록(list)을 만들어. scanl1과 scanr1도 있고, 이건 foldl1, foldr1과 비슷해.

  1. ghci> scanl (+) 0 [3,5,2,1]  
  2. [0,3,8,10,11]  
  3. ghci> scanr (+) 0 [3,5,2,1]  
  4. [11,8,3,1,0]  
  5. ghci> scanl1 (\acc x -> if x > acc then x else acc) [3,4,5,3,7,9,2,1]  
  6. [3,4,5,5,7,9,9,9]  
  7. ghci> scanl (flip (:)) [] [3,2,1]  
  8. [[],[3],[2,3],[1,2,3]]  

 scanl을 쓸 때, 최종 결과는 결과 목록(list)의 마지막 원소가 되고, scanr에서는 최종 결과가 목록(list)의 첫번째 원소가 돼.

 scan은 fold로 구현할 수 있는 함수의 중간 과정을 살펴보고 싶을 때 사용돼. 이 질문에 대답해보자. 자연수의 제곱근의 합을 순서대로 몇 개를 더하면 1000이 넘을까? 모든 자연수의 제곱근 목록(list)을 얻기 위해, map sqrt [1..]을 수행하면 돼. 이제, 합을 얻기 위해 fold를 쓸 수도 있지만, 지금은 합이 어떤 과정으로 수행되는지에 관심이 있기 때문에, scan을 써야 해. 한 번 scan이 끝나고 나면, 다 더해서 1000보다 작은 합이 몇 개나 존재하는지 알 수 있어. scan한 목록(list)의 첫번째 값은 당연히 1이 될거야. 두번째 값은 1 + 2의 제곱근이 될거고. 세 번째 값은 1 + 2의 제곱근 + 3의 제곱근이 되겠지. 어떤 X개의 합이 1000이하라면, 1000이 넘을 때까지 x+1의 합을 구하겠지.

  1. sqrtSums :: Int  
  2. sqrtSums = length (takeWhile (<1000) (scanl1 (+) (map sqrt [1..]))) + 1  


  1. ghci> sqrtSums  
  2. 131  
  3. ghci> sum (map sqrt [1..131])  
  4. 1005.0942035344083  
  5. ghci> sum (map sqrt [1..130])  
  6. 993.6486803921487  

 filter는 무한 목록(list)에 대해 동작하지 못하기 때문에 takeWhile을 썼어. 우리야 list가 증가 순인지 알지만, filter는 모르잖아. 그래서 scan한 목록(list)을 합이 1000 넘는 시점에서 잘라내기 위해 takeWhile을 썼어.


$를 이용한 함수 적용(function application with $)


 좋아, 다음으로는 $ 함수에 대해 알아볼거야. 이건 함수 적용(function application) 이라고 불려. 먼저, 이게 어떻게 정의되어 있는지 살펴보자.

  1. ($) :: (a -> b) -> a -> b  
  2. f $ x = f x  

 뭐야 이거? 뭐 이딴 쓸모 없는 연산자가 다 있어? 이건 그냥 함수를 실행할 뿐이야! 음, 거의 맞지만, 약간 달라! 일반적인 함수 적용(두 개체 사이에 공백을 둬서 실행하는)이 가장 높은 우선 순위를 갖고 있는 반면에, $ 함수는 가장 낮은 우선순위를 갖고 있어. 공백을 이용한 함수 적용이 좌측 결합을 하는 반면에(그래서 f a b c는 ((f a) b) c)와 같지), $를 이용한 함수 적용은 우측 결합을 해.

 그래 다 좋은데, 이게 그래서 어떤 도움이 되는데? 대부분의 경우, 이건 과도하게 많은 소괄호를 쓰지 않게 해주기 때문에 굉장히 편리한 함수야. 표현식 sum (map sqrt [1..130])을 생각해보자. $가 낮은 우선순위를 갖고 있기 때문에, 이 표현식을 sum $ map sqrt [1..130]으로 바꿔쓸 수 있고, 이건 타자를 칠 부담을 덜어주지! $을 만났을 때, 그 오른쪽의 표현식은 왼쪽 함수에 적용이 돼. sqrt 3 + 4 + 9 는 어떨까? 이건 9와 4, 그리고 3의 제곱근을 더해. 만약 3+4+9의 제곱근을 구하고 싶다면, sqrt (3+4+9)라고 쓰거나 $을 이용해서 sqrt $ 3 + 4 + 9라고 써야하지. 왜냐하면 $ 함수는 어떤 연산보다도 낮은 우선순위를 갖고 있거든. 그래서 $함수를 여는 소괄호를 쓰고, 표현식의 맨 끝에 닫는 소괄호를 쓰는 거랑 같다고 생각할 수 있어.

 sum (filter (>10) (map (*2) [2..10]))은 어떨까? 음, $가 우측 결합이기 때문에, f (g ( z x))는 f $ g $ z x랑 똑같아. 따라서, sum (filter (>10) (map (*2) [2..10]))은 sum $ filter (>10) $ map (*2) [2..10]이랑 같지.

 하지만 소괄호를 지우는 것에서 떠나, $는 함수 적용을 뜻하는, 그냥 다른 함수랑 똑같은 하나의 함수로 취급돼. 따라서, 예를 들어 map 함수 적용을 함수의 목록(list) 전체에 대해 수행할 수도 있어.

  1. ghci> map ($ 3) [(4+), (10*), (^2), sqrt]  
  2. [7.0,30.0,9.0,1.7320508075688772]  


 합성 함수(Function composition)


 수학에서, 합성 함수는 이렇게 정의돼.  , 이건 두 함수가 하나로 합해져서, 어떤 인자 x를 이용해 호출됐을 때, 함수 g를 x를 인자로 써서 호출해 얻은 결과 값에 다시 f 함수를 적용시킨 결과를 내놓는 새로운 함수를 의미하지.

 Haskell에서, 합성 함수는 이거랑 완전 똑같아. 합성 함수는 . 함수를 통해 얻을 수 있고, 이 함수는 다음과 같이 정의되어 있어.

  1. (.) :: (b -> c) -> (a -> b) -> a -> c  
  2. f . g = \x -> f (g x)  

 형(型) 서명을 염두에 둬. f는 반드시 g의 돌려주는 값과 같은 형(型)의 값을 인자로 받아야 해. 따라서 결과 함수는 g의 인자와 같은 형(型)의 인자를 받아서, f의 돌려주는 형(型)과 같은 형(型)의 값을 돌려주게 되지. 표현식 negate . (* 3)은 숫자를 인자로 받아서, 그 값에 3을 곱해서 부호를 바꾼 값을 돌려줘.

 합성 함수의 쓰임새중 하나는 즉석에서 함수를 만들어 그걸 다른 함수로 넘기는 거야. 물론, 람다를 쓸 수도 있지만, 대부분의 경우 합성 함수가 더 명확하고 간결해. 숫자 목록(list)이 있고 그걸 전부 음수로 바꾼 목록(list)을 얻고 싶다고 하자. 각 숫자들의 절댓값을 구해서 그걸 음수로 바꾼 결과를 얻으면 되겠지. 이런 식으로 말야.

  1. ghci> map (\x -> negate (abs x)) [5,-3,-6,7,-3,2,-19,24]  
  2. [-5,-3,-6,-7,-3,-2,-19,-24]  

 저 람다를 합성 함수로 어떻게 바꿀 수 있을지 생각해봐. 합성 함수를 쓰면 이렇게 바꿔쓸 수 있어.

  1. ghci> map (negate . abs) [5,-3,-6,7,-3,2,-19,24]  
  2. [-5,-3,-6,-7,-3,-2,-19,-24]  

 엄청나지! 합성 함수는 우측 결합이기 때문에, 얼마든지 많은 함수들을 한 번에 합성할 수 있어. 표현식 f(g (z x))는 (f . g . z) x랑 똑같아. 이걸 이용해서,

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

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

로 바꿀 수 있지. 하나의 함수가 여러 개의 인자를 받는 경우는 어떻까? 음, 이걸로 합성 함수를 만들고 싶다면, 보통 부분 적용을 이용해 그걸 하나의 인자만 받는 함수로 바꿔서 써야해. sum (replicate 5 (max 6.7 8.9))는 (sum . replicate 5 . max 6.7) 8.9 또는 sum . replicate 5 . max 6.7 $ 8.9로 바꿔쓸 수 있지. 이 때 내부적으로는 다음과 같은 일이 일어나. 우선 max 6.7 함수를 수행한 결과에 replicate 5를 적용하는 함수를 만들어. 그리고, 그 함수의 결과르 취해 전체 합을 구하는 함수를 만들어내지. 마지막으로, 이 함수에 8.9를 적용시켜. 하지만 일반적으로는, 이렇게 읽을 수 있어. 8.9를 max 6.7에 적용시키고, 그 다음 그 결과를 replicate 5에 적용시키고, 마지막으로 그 결과에 다시 sum을 적용시킴. 합성 함수를 이용해 소괄호가 많은 표현식을 바꿔쓰고 싶다면, 먼저 가장 안쪽 함수의 마지막 인자를 $ 뒤에 적는 걸로 시작해. 그리고 나머지 함수 호출을 마지막 인자를 생략한 채로 적고, 그 사이에 .을 적어. replicate 100 (product (map (*3) (zipWith max [1,2,3,4,5] [4,5,6,7,8])))을 바꿔써보자. 이건 replicate 100 . product . map (*3) . zipWith max [1,2,3,4,5] $ [4,5,6,7,8]로 쓸 수 있어. 표현식이 세 개의 소괄호로 끝나니까, 이걸 합성 함수로 바꾸려면 세 개의 함수 합성 연산자가 있어야 해.

 합성 함수의 다른 일반적인 사용법은 함수를 무인자 정의(point-free style, 인자가 없는 정의)하는 거야. 이전에 만든 함수 하나를 보자.

  1. sum' :: (Num a) => [a] -> a     
  2. sum' xs = foldl (+) 0 xs     

 xs는 양쪽 모두에서 우변이기 때문에, 커링에 의해서 xs를 양쪽에서 생략해도 돼. 왜냐하면 foldl (+) 0은 목록(list)을 취하는 함수를 만들어내니까. 함수를 sum' = foldl (+) 0 과 같은 방식으로 쓰는 걸 무인자 정의라고 해. 아래 함수를 무인자 정의하려면 어떻게 해야할까?

  1. fn x = ceiling (negate (tan (cos (max 50 x))))  

 x를 그냥 양쪽에서 다 제거 할 수는 없어. 함수 본체의 x 오른쪽에 소괄호가 있기 때문이지. cos (max 50)같은 건 말이 안 되잖아. 어떤 함수의 cosine 값을 얻을 수는 없지. fn을 합성함수를 이용해 다음처럼 표현할 수 있어.

  1. fn = ceiling . negate . tan . cos . max 50  

 훌륭해! 대부분의 경우, 무인자 정의한 함수가 훨씬 읽기 좋고 간결해. 왜냐하면 이건 데이터에 대해, 그리고 데이터를 어떻게 다뤄야할지 생각하기보단 함수 자체에 대해, 그리고 함수가 합성된 결과가 뭔지에 대해 더 생각하게 만들거든. 간단한 함수를 취해 그걸 합성함으로써 더 복잡한 함수를 만들 수 있어. 하지만 대부분의 경우, 함수를 무인자 정의하는 게 함수가 많이 복잡한 경우에는 읽기가 불편해. 나는 때로 길게 합성을 하는 게 잘못인 줄 알면서도 그렇게 하는 걸 좋아하지만, 어쨌든 그래서 함수 합성을 길게 연달아 쓰는 건 보통 권장되지 않아. 선호되는 스타일은 let 절을 이용해 중간 값에 이름을 붙이거나 문제를 부분 문제로 나눠 각각을 합치는 거야. 이게 커다란 합성의 연속으로 함수를 만드는 것보다는 더 읽기 좋겠지.

 map과 filter 섹션에서, 10,000보다 작은 모든 홀수 제곱수의 합을 찾는 문제를 풀었었지. 여기 그걸 함수 형태로 나타낸 해법이 있어.

  1. oddSquareSum :: Integer  
  2. oddSquareSum = sum (takeWhile (<10000) (filter odd (map (^2) [1..])))     

 합성함수의 애호가가 되기 위해, 이걸 이렇게 바꿔쓸 수 있어.

  1. oddSquareSum :: Integer  
  2. oddSquareSum = sum . takeWhile (<10000) . filter odd . map (^2) $ [1..]  

 하지만, 누군가 이 명령문(code)을 읽을 가능성이 있다면 난 아마 이 함수를 이런 식으로 쓸 거야.

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

 이건 어떤 명령문(code) 골프 대회 ( * 역주 : 짧은 명령문 작성(short coding), 그러니까 명령문(code) 길이를 최대한 짧게 만드는 방법을 겨루는 대회를 말합니다.)에서도 우승할 수 없겠지만, 이 명령문 읽는 사람은 아마 합성 함수의 연속보다는 이게 훨씬 읽기 좋다는 걸 알겠지.


Higher order functions

Haskell functions can take functions as parameters and return functions as return values. A function that does either of those is called a higher order function. Higher order functions aren't just a part of the Haskell experience, they pretty much are the Haskell experience. It turns out that if you want to define computations by defining what stuff is instead of defining steps that change some state and maybe looping them, higher order functions are indispensable. They're a really powerful way of solving problems and thinking about programs.

Curried functions

Every function in Haskell officially only takes one parameter. So how is it possible that we defined and used several functions that take more than one parameter so far? Well, it's a clever trick! All the functions that accepted several parameters so far have been curried functions. What does that mean? You'll understand it best on an example. Let's take our good friend, themax function. It looks like it takes two parameters and returns the one that's bigger. Doing max 4 5 first creates a function that takes a parameter and returns either 4 or that parameter, depending on which is bigger. Then, 5 is applied to that function and that function produces our desired result. That sounds like a mouthful but it's actually a really cool concept. The following two calls are equivalent:

  1. ghci> max 4 5  
  2. 5  
  3. ghci> (max 45  
  4. 5  

Putting a space between two things is simply function application. The space is sort of like an operator and it has the highest precedence. Let's examine the type of max. It'smax :: (Ord a) => a -> a -> a. That can also be written asmax :: (Ord a) => a -> (a -> a). That could be read as: max takes an a and returns (that's the ->) a function that takes an a and returns an a. That's why the return type and the parameters of functions are all simply separated with arrows.

So how is that beneficial to us? Simply speaking, if we call a function with too few parameters, we get back a partially applied function, meaning a function that takes as many parameters as we left out. Using partial application (calling functions with too few parameters, if you will) is a neat way to create functions on the fly so we can pass them to another function or to seed them with some data.

Take a look at this offensively simple function:

  1. multThree :: (Num a) => a -> a -> a -> a  
  2. multThree x y z = x * y * z  

What really happens when we do multThree 3 5 9 or ((multThree 3) 5) 9? First, 3 is applied to multThree, because they're separated by a space. That creates a function that takes one parameter and returns a function. So then 5 is applied to that, which creates a function that will take a parameter and multiply it by 15. 9 is applied to that function and the result is 135 or something. Remember that this function's type could also be written asmultThree :: (Num a) => a -> (a -> (a -> a)). The thing before the -> is the parameter that a function takes and the thing after it is what it returns. So our function takes an a and returns a function of type (Num a) => a -> (a -> a). Similarly, this function takes an a and returns a function of type (Num a) => a -> a. And this function, finally, just takes ana and returns an a. Take a look at this:

  1. ghci> let multTwoWithNine = multThree 9  
  2. ghci> multTwoWithNine 2 3  
  3. 54  
  4. ghci> let multWithEighteen = multTwoWithNine 2  
  5. ghci> multWithEighteen 10  
  6. 180  

By calling functions with too few parameters, so to speak, we're creating new functions on the fly. What if we wanted to create a function that takes a number and compares it to 100? We could do something like this:

  1. compareWithHundred :: (Num a, Ord a) => a -> Ordering  
  2. compareWithHundred x = compare 100 x  

If we call it with 99, it returns a GT. Simple stuff. Notice that the x is on the right hand side on both sides of the equation. Now let's think about what compare 100 returns. It returns a function that takes a number and compares it with 100. Wow! Isn't that the function we wanted? We can rewrite this as:

  1. compareWithHundred :: (Num a, Ord a) => a -> Ordering  
  2. compareWithHundred = compare 100  

The type declaration stays the same, because compare 100 returns a function. Compare has a type of(Ord a) => a -> (a -> Ordering) and calling it with 100 returns a (Num a, Ord a) => a -> Ordering. The additional class constraint sneaks up there because 100 is also part of the Num typeclass.