[Learn You a Haskell For Great Good!] 5. 재귀

Learn You a Haskell For Great Good!

이 게시글은 http://learnyouahaskell.com/chapters 사이트에 올라와있는 글을 한글로 번역한 것입니다.의역이 굉장히 많으니 주의...

5. 재귀

재귀야 안녕!

 이전 챕터에서 재귀에 대해 간략하게 언급했었지. 이번 챕터에서는 재귀가 왜 Haskell에서 중요하고, 재귀적으로 생각함으로써 어떻게 문제를 간결하고 우아하게 풀 수 있는 지 살펴보는 등, 재귀에 대해 좀 더 자세히 알아볼거야. 

 아직도 재귀가 뭔지 모르겠다면, 이 문장을 읽어봐. 하하! 농담이야. 재귀는 그 자체의 정의를 해당 함수 내에 적용시킴으로써 그 함수를 정의하는 방법이야. 수학에서 정의는 종종 재귀적으로 주어져. 예를 들어서, 피보나치 수열은 재귀적으로 정의되어 있어. 첫번째로, 처음 두 개의 피보나치 숫자는 재귀적이지 않아. F(0) = 0, F(1) =1 로 정의되고, 이건 0번째, 1번째 피보나치 수가 각각 0과 1이라는 뜻이야. 그리고나선 임의의 자연수에 대해, 피보나치 숫자는 그 이전의 두 피보나치 숫자의 합이라고 정의하지. 따라서 F(n) = F(n-1) + F(n-2)가 돼. 이런식으로 F(3) = F(2)+F(1)이 되고, 이건 (F(1)+F(0))+F(1)과 같겠지. 여기서 피보나치 수 중에 재귀적으로 정의되지 않은 부분까지 내려갔기 때문에, F(3)은 2라고 안전하게 이야기할 수 있어. 재귀에서 한 두개 정도 재귀적으로 정의되지 않는 부분(F(0)과 F(1)처럼)을 경계조건(edge condition)이라고 해. 그리고 이건 재귀적인 함수가 종료되게 하는 것에 중요한 역할을 하지. F(0)과 F(1)을 비재귀적으로 정의하지 않는다면, 모든 숫자가 0에 도달하고 나서도 계속해서 음수까지 내려가버리기 때문에 어떠한 해도 얻을 수 없어. 갑자기, F(-2000) = F(-2001) + F(-2002)라고 말할 수 있고 이런 반복은 절대 끝나지 않겠지!

 명령형 언어에서와는 다르게, Haskell에서는 어떻게 그걸 얻을 것이냐(how you get it) 대신에 뭐가 어떻다(what something is) 라고 정의함으로써 연산을 수행하기 때문에, 재귀가 중요해. 그래서 Haskell에서는 while 루프나 for 루프가 없고, 대신에 뭐가 어떤 건지 정의하기 위해 몇번이고 재귀를 써야하는 거지.

 Maximum awesome

 maximum 함수는 정렬될 수 있는 어떤 개체들(Ord 타입 클래스에 속하는 것들)의 리스트를 받아서 그 중에 가장 큰 걸 돌려줘. 명령형 스타일로 이 함수를 어떻게 구현하는 지 생각해봐. 아마 먼저 최댓값을 저장할 변수를 하나 만들고, 리스트의 전체 요소들을 순회하면서 현재 최댓값보다 큰 숫자를 발견하면 최댓값을 그 숫자로 갱신하는 과정을 반복하겠지. 맨 마지막까지 돌고 나서 저장된 최댓값이 결과가 될 거고. 후! 몇 단어 정도로 충분히 서술 가능한 정말 단순한 알고리즘이지!

 이제 이걸 재귀적으로 어떻게 정의해야할 지 알아보자. 먼저 원소가 하나 뿐인 리스트의 최댓값은 바로 그 원소의 값과 같다 라고 경계 조건(edge condition)을 정할 수 있어. 그리고 이것보다 길이가 긴 리스트에 대해, 해당 리스트의 최댓값은 그 리스트의 head의 값과, 그 리스트의 tail의 최댓값 둘 중 더 큰 값이라고 정의할 수 있지. 이게 다야! Haskell로 이걸 구현해보자.

1. maximum' :: (Ord a) => [a] -> a  
2. maximum' [] = error "maximum of empty list"  
3. maximum' [x] = x  
4. maximum' (x:xs)   
5.     | x > maxTail = x  
6.     | otherwise = maxTail  
7.     where maxTail = maximum' xs  

 보다시피, 패턴매칭은 재귀함수랑 잘 어울려! 패턴 매칭이 없는 대부분의 명령형 언어에선 경계 조건을 테스트하기 위해 많은 if else 구문을 써야하지. Haskell에선, 그냥 그것들을 패턴으로 써버리면 돼. 그래서 첫번째 경계조건은 리스트가 텅 비어 있을 때를 이야기하고, 이건 크래쉬(crash)를 일으키지. 텅 빈 리스트의 최댓값을 어떻게 결정하겠어? 두 번째 패턴 역시 경계조건이야. 이건 원소가 하나뿐인 리스트는 최댓값으로 그 원소의 값을 돌려준다는 걸 의미하지.

 세번째 패턴이 실제 동작이 일어나는 부분이야. 패턴 매칭을 이용해서 리스트를 head와 tail로 분리했어. 이건 재귀에서 리스트를 다룰 때 가장 일반적인 관용구 같은 거니, 익숙해지는 게 좋아. maxTail을 리스트의 나머지 부분의 최댓값으로 정의하기 위해 where 절을 사용했어. 이를 이용해서 head가 list의 나머지 부분의 최댓값(maxTail)보다 더 크다면 head를 리턴하고, 그렇지 않다면 maxTail을 리턴하는거지.

 이제 예시 숫자 리스트 [2,5,1]을 통해 이게 잘 동작하는 지 확인 해보자. 이 리스트에 대해 maximum'을 호출하면, 일단 처음 두 개의 패턴은 매칭이 안 되겠지. 세번째 패턴에서 매칭이 될거고, 리스트는 2와 [5,1]로 분리돼. where 절에서 maxTail을 구하려면 다시 maximum' [5,1]의 결과를 알아야 될거야. 따라서 [5,1]에 대해 다시 maximum' 함수를 호출하게 되고, 이 리스트 역시 세 번째 패턴에서 매칭되며 5와 [1]로 분리되겠지. 이제, where 절은 [1]의 최댓값을 알고 싶어할 거야. 그리고 경계조건에 의해서, [1]에 대한 maximum' 함수의 호출은 1을 리턴하게 되겠지. 최종적으로, 5와 [1]의 최댓값(1)을 비교해서 그 중 큰 값인 5를 리턴할거야. 이제 [5,1]의 최댓값이 5라는 걸 알았으니, 다시 한 번 더 올라가서 2와 [5,1]의 최댓값인 5를 비교하겠지. 그 결과로 [2,5,1]의 최댓값이 5라는 걸 알 수 있어.

 이 함수는 max 함수를 이용하면 더 명확하게 쓸 수 있어. max함수는 숫자 두 개를 인자로 받아 그 중 큰 걸 돌려주는 함수였지. max를 이용해 maximum' 함수를 이렇게 바꿔쓸 수 있어.

1. maximum' :: (Ord a) => [a] -> a  
2. maximum' [] = error "maximum of empty list"  
3. maximum' [x] = x  
4. maximum' (x:xs) = max x (maximum' xs)  

 정말 우아한 코드지! 본질적으로, 어떤 리스트의 최댓값은 그 리스트의 첫번째 원소와, 나머지의 최댓값중 더 큰 값이야.

 몇 가지 다른 재귀 함수들

 이제 우린 재귀적으로 생각하는 일반적인 방법을 알아. 그러니까 재귀를 이용한 함수를 몇 개 더 구현해보자. 우선, 우리는 replicate 함수를 구현해볼거야. replicate는 Int와 어떤 인자를 받아서 해당 원소가 n개만큼 반복된 리스트를 돌려줘. 예를 들어서, replicate 3 5 는 [5,5,5]를 리턴하지. 이제 경계 조건에 대해서 생각해보자. 경계 조건은 아마 0 또는 0 보다 작은 경우가 될 거야. 만약 어떤 걸 0번 만큼 반복하는 리스트를 만들고 싶다면, 텅 빈 리스트를 돌려줘야겠지. 음수인 경우도 마찬가지 일거고.

1. replicate' :: (Num i, Ord i) => i -> a -> [a]  
2. replicate' n x  
3.     | n <= 0    = []  
4.     | otherwise = x:replicate' (n-1) x  

 여기선 논리 조건식을 이용해 검사하기 때문에 패턴 대신에 가드를 이용했어. 만약 n이 0 이하라면, 이건 텅 빈 리스트를 돌려줘. 그렇지 않다면 x를 첫 번째 원소로 가지고 x를 n-1번 반복한 걸 나머지 원소로 갖는 리스트를 리턴하지. 결과적으로, (n-1)이 반복되면 경계조건에 도달하게 되겠지

 주: Num은 Ord의 서브 클래스가 아냐. 무슨 뜻이냐면 숫자를 구성하는 타입은 꼭 정렬되어야 할 이유는 없다는 거야. 그래서 덧셈, 뺄셈 뿐만 아니라 비교까지 하고 싶다면 Num과 Ord 클래스 제약조건을 모두 가져야한다고 명시해야만 해.

 다음으로, take 함수를 구현해볼거야. 이건 리스트로부터 정해진 개수의 원소를 추출해내지. 예를 들어, take 3 [5,4,3,2,1]은 [5,4,3]을 리턴해. 만약 0 또는 그보다 작은 개수의 원소를 리스트로부터 추출하려고 한다면, 텅 빈 리스트를 얻게 될거야. 또 텅 빈 리스트로부터 원소를 추출하려고 해도 마찬가지로 텅빈 리스트를 얻게 될거고. 이 두 가지 케이스가 여기서는 경계 조건을 이뤄. 이제 한 번 구현해 보자.

1. take' :: (Num i, Ord i) => i -> [a] -> [a]  
2. take' n _  
3.     | n <= 0   = []  
4. take' _ []     = []  
5. take' n (x:xs) = x : take' (n-1) xs  

 첫번째 패턴은 우리가 0또는 음수 개의 원소를 추출하려고 할 때의 경우야. 리스트가 어떻게 구성되어 있는지 이 경우에서는 전혀 신경쓰지 않아도 되기 때문에 _을 이용했어. 여기서도 가드를 이용했지만, otherwise는 쓰지 않았다는 것에 주의해. 무슨 뜻이냐면 n이 0보다 클 경우엔, 매칭은 실패하고 다음 패턴으로 넘어간다는 거야. 두 번째 패턴은 우리가 텅 빈 리스트에서 어떤 걸 추출하려고 한다면, 텅빈 리스트를 얻게 된다는 걸 말하고 있어. 세 번째 패턴은 리스트를 head와 tail로 나누고, 리스트에서 n개의 원소를 추출하는 건 리스트의 head를 추출하고, 그 뒤에 리스트의 tail에서 n-1개의 원소를 추출해서 붙이는 것과 같다는 걸 말해. 종이에 [4,3,2,1]로부터 3개를 추출하는 과정이 어떤식으로 이루어지는 지 한 번 적으면서 확인해봐.

 reverse는 단순히 리스트를 뒤집어 줘. 경게조건에 대해 생각해봐. 어떤게 될까? 음... 그건 텅빈 리스트인 경우겠지!  텅 빈 리스트는 뒤집어봤자 텅빈 리스트니까 말야. 좋아. 나머지 경우는? 리스트를 head와 tail로 나눠서, tail을 뒤집은 것 뒤에 head를 붙이면 해당 리스트를 뒤집은 리스트를 얻을 수 있겠지.

1. reverse' :: [a] -> [a]  
2. reverse' [] = []  
3. reverse' (x:xs) = reverse' xs ++ [x]  

 자! 계속해볼까.

 Haskell은 무한대 크기의 리스트를 지원하기 때문에, 재귀가 꼭 경계조건을 가져야할 필요는 없어. 하지만 경계 조건이 없다면, 이건 결과를 무한히 뿜어내거나 혹은 무한대 크기의 리스트처럼 무한한 데이터 구조를 생산해낼거야. 무한대 크기의 리스트가 좋은 점은 우리가 그걸 원하는 위치에서 자를 수 있다는 거야. repeat는 원소를 받아서 그걸 무한히 반복한 리스트를 돌려주지. 이걸 재귀적으로 구현하는 건 정말 쉬워. 봐봐.

1. repeat' :: a -> [a]  
2. repeat' x = x:repeat' x  

 repeat 3을 호출하는 건 3으로 시작하고 3을 무한한 크기만큼 반복하는 걸 그 tail로 갖는 리스트를 돌려줘. 따라서 repeat 3을 호출하는 건 3:repeat 3, 혹은 3:(3:repeat 3), ...을 호출하는 것과 똑같이 평가될거야. repeat 3은 절대 평가가 끝나지 않을테지만, take 5 (repeat 3)은 3이 5개 있는 원소를 돌려주겠지. 이건 replicate 5 3을 수행하는 것과 비슷해.

 zip은 두 개의 리스트르 받아서 그걸 하나로 합쳐줘. zip은 길이가 더 짧은 리스트에 맞춰 잘라내기 때문에 zip [1,2,3] [2,3] 은 [(1,2), (2,3)]을 돌려주지. 텅빈 리스트와 다른 리스트를 zip하려고 하면 어떻게 될까? 당연히 텅빈 리스트를 얻게 될거야. 따라서 이게 경계 조건이 되겠지. zip은 두 개의 리스트를 인자로 받기 때문에 경계 조건도 두 개가 되어야 할 거야.

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

 처음 두 개의 패턴은 두 리스트 중 하나가 텅빈 리스트인 경계 조건일 때를 말해. 세 번째 패턴은 두 리스트를 zip하는 건 head를 한 쌍으로 만들고 그 뒤에 두 리스트의 tail을 zip한 리스트를 붙이는 것과 같다는 거야. [1,2,3]과 ['a','b']를 zip한다면 맨 마지막엔 [3]과 []을 zip하는 케이스에 도달하겠지. 경계 조건은 이 경우에 []를 리턴할 테고, 따라서 최종 결과는 (1,'a'):(2,'b'):[]가 되고 이건 [(1,'a'),(2,'b')]랑 똑같지.

 표준 라이브러리 함수 하나만 더 구현해보자. elem은 원소와 리스트를 받아서 그 원소가 리스트에 속하는 원소인지를 확인해. 경계조건은 텅 빈 리스트일 때가 될거야. 리스트를 다루는 함수에서 제일 흔한 케이스지. 텅 빈 리스트는 어떤 원소도 갖지 않고 있을테니까, 이건 명백하게 우리가 찾고 있는 원소를 포함하지 않을거야.

1. elem' :: (Eq a) => a -> [a] -> Bool  
2. elem' a [] = False  
3. elem' a (x:xs)  
4.     | a == x    = True  
5.     | otherwise = a `elem'` xs   

 정말 간단하지. head가 찾고 있는 원소가 아니라면 tail을 검사해. 만약 텅빈 리스트에 도달한다면, 결과는 False가 되지.

Quick, sort!

 정렬될 수 있는 요소들의 리스트가 있어. 걔네들의 타입은 Ord 타입클래스에 속해있지. 그리고 난 얘들을 정렬하고 싶어! 정렬에는 퀵 소트라고 불리는 정말 멋진 알고리즘이 있어. 이건 정말 똑똑한 방식으로 정렬해. 명령형 언어에서는 퀵 소트를 구현하기 위해 10줄 이상의 코딩이 필요하지만, Haskell에서는 더 짧고 우아한 방식으로 구현할 수 있어. 퀵 소트는 Haskell에서 정렬을 하는 전형적인 방법이 될거야. Haskell에서는 이게 모든 사람들이 단지 Haskell이 얼마나 우아한지 보여주기 위한 걸로 생각하기 때문에 퀵 소트를 구현하는 건 Haskell에서 정말 싸구려같은 짓으로 여겨지지만, 어쨌든 한 번 구현해보자. 

 그래서, quicksort의 타입 서명은 quicksort :: (Ord a) => [a] -> [a] 가 될 거야. 별로 놀라울 건 없지. 경계 조건은? 텅 빈 리스트야. 텅 빈 리스트를 정렬하면 텅 빈 리스트가 되겠지. 메인 알고리즘은 다음과 같아. '정렬된 리스트는 리스트의 head보다 작거나 같은 원소들을 정렬한 내용을 맨 앞에 두고, 그 뒤에 리스트의 head 값이 온 다음, 마지막으로는 head보다 더 큰 원소들을 정렬한 내용을 뒤에 오게 만든 것이다.' 정의에 의해 우리는 두 번 정렬 과정을 거쳐야 해. 따라서 재귀 호출도 두 번 일어나겠지! 알고리즘을 정의할 때 이걸 해라, 그걸 해라, 그 다음에 저걸 해라... 같은게 아니라 이건 ~이다 라는 말을 써서 정의해야 한다는 걸 잊지마. 이게 함수형 언어의 아름다움이거든! 어떻게 리스트의 head보다 작은 원소들 더 큰 원소들을 걸러낼 수 있을까? 조건 제시형 리스트를 이용하면 돼. 자, 함수의 정의를 한 번 보자.

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

 이게 잘 동작하는 지 확인하기 위해 작은 테스트를 한 번 해보자.

1. ghci> quicksort [10,2,5,3,1,6,7,4,2,3,4,8,9]  
2. [1,2,2,3,3,4,4,5,6,7,8,9,10]  
3. ghci> quicksort "the quick brown fox jumps over the lazy dog"  
4. "        abcdeeefghhijklmnoooopqrrsttuuvwxyz"  

 야호! 우리가 얘기했던 그대로야! [5,1,9,4,6,7,3]을 예로 들어서 정렬하는 과정을 한 번 살펴보자. 알고리즘은 처음으로 리스트의 head를 취해. 그건 5가 될거고, 이제 이걸 자기보다 작은 원소들의 리스트와 더 큰 원소들의 리스트 사이에 끼워넣어야 해. 이 시점에서, [1,4,3] ++ [5] ++ [9,6,7] 의 형태가 되겠지. 일단 정렬 한 번이 성공적으로 완료됐어. 이제 5는 리스트의 4번째 위치에 오게 될거야. 왜냐하면 자기보다 작은 원소가 3개고, 더 큰 원소도 3개니까. 이제, [1,4,3]과 [9,6,7]을 정렬하면, 완전히 정렬된 리스트를 얻을 수 있어! 이 리스트들도 똑같은 함수를 이용해서 재귀적으로 정렬하게 될거야. 결과적으로, 텅 빈 리스트까지 도달하게 될거고 텅빈 리스트는 그 자체로 정렬된 리스트기 때문에 여기서 재귀 호출이 종료되겠지. 여기 그 과정을 그린 그림이 있어.

 그림에서, 정렬이 완료돼서 더 이상 위치가 바뀌지 않는 원소들은 오렌지 색으로 나타냈어. 오렌지 색 원소들을 왼쪽부터 오른쪽으로 순서대로 읽으면 그게 바로 정렬된 리스트가 돼. 정렬을 할 때에는 항상 다른 원소들과 비교를 할 기준이 필요해. 퀵소트에서는 기준으로 리스트의 head를 이용하고 있지. 이걸 피벗(pivot)이라고 불러. 이건 초록색으로 나타냈어. 여기서 피벗으로 head를 쓰는 이유는 이게 패턴 매칭에 적용시키기 쉽기 때문이야. 피벗보다 작거나 같은 원소들은 밝은 초록색으로 나타냈고, 피벗보다 큰 원소들은 어두운 초록색으로 나타냈어. 노란 배경색으로 칠해진 리스트들은 퀵소트의 수행 대상이 되는 리스트들을 말해.

재귀적으로 생각하기

 여기까지 재귀를 어느 정도 다뤄봤고, 아마 눈치챘겠지만 재귀적인 함수를 짜는데에는 일종의 패턴이 있어. 대부분의 경우 경계조건을 정의하고, 어떤 원소와, 그 나머지 원소들에 대해 적용되는 함수 사이에 어떤 것을 하는 함수를 정의하는 과정으로 진행되는 거지. 그게 꼭 리스트여야할 필요는 없어. 트리든 어떤 다른 자료구조드 상관없어. 합계는 리스트의 첫번째 원소와 나머지 원소들의 합계의 합이지. 리스트의 곱은 첫번째 원소와 리스트의 나머지 원소들의 곱의 곱이고. 리스트의 길이는 1과 리스트의 tail의 길이를 더한거고, 그 외 기타 등등...

 물론, 얘네들은 경계조건을 가지지. 대부분의 경우 경계조건은 재귀 함수가 적용되는게 말이 안되는 경우를 나타낸 거야. 리스트를 다룰 때, 가장 흔한 경계조건은 텅 빈 리스트지. 트리를 다루는 경우엔, 아마 경계조건은 거의 대부분 어떤 자식도 가지지 않은 노드일 때가 될 거야.

 숫자를 가지고 재귀적으로 다룰 때에도 비슷해. 보통 어떤 숫자와 수정된 숫자에 적용되는 함수를 다루지. 이미 우린 팩토리얼 함수를 만들어봤고, 이건 어떤 숫자와 그 숫자보다 1작은 숫자의 팩토리얼의 곱으로 정의돼. 이런 재귀의 적용은 0인 경우에는 당연히 말이 안 되겠지. 팩토리얼은 양의 정수에 대해서만 정의되니까. 종종 경계 조건의 값은 항등원(identity)이 돼. 곱셈의 항등원은 1이야. 어떤 숫자와 1을 곱하면 그 숫자 자체가 나오기 때문이지. 어떤 리스트의 합을 다룰 때에는, 우리는 텅빈 리스트의 합을 0으로 정의할 수 있어. 왜냐하면 덧셈의 항등원은 0이니까. 퀵소트에서, 경계조건은 텅 빈 리스트고, 그 항등원 역시 텅빈 리스트야. 왜냐하면 텅 빈 리스트를 리스트에 더하면, 원래 리스트 그 자체가 나오기 때문이지.

 따라서 어떤 문제를 풀 때 재귀적인 방법으로 생각하는 걸 시도할 때는, 재귀적인 해법이 적용되지 않는 경우에 대해 생각하고, 그걸 경계조건으로 쓸 수 있는지 보고, 항등원에 대해서 생각해보고, 그리고 함수의 인자들을 여러 부분으로 나눌 수 있는지 아닌지 생각해보고(예를 들어, 리스트는 종종 패턴 매칭을 통해 head와 tail로 분리가 되지), 어떤 부분에 재귀 호출을 써야하는 지 생각해봐야해.