[Haskell Tutorial] Recursion

 

📌 반복문 대신 재귀로

Haskell 에서는 반복을 수행하기 위해 loop 를 순회하는 것이 아니라 재귀 를 활용합니다.

 

📌 Tail Call Elimination

일반적으로 프로그래밍 언어에서 재귀호출 은 콜스택을 쌓기 때문에 메모리 이슈가 발생할 가능성이 있습니다.

하지만 Haskell 과 같은 함수형 언어에서는 Tail-Call Elimination 를 통해 최적화를 수행합니다.

 

📌 Lazy Evaluation

Haskell 은 지연 평가를 통해 실행됩니다.

따라서 값이 필요한 시점에 평가를 하며 필요하지 않다면 평가하지 않습니다.

 

📌 예제로 익히기

maximum 은 리스트의 요소 중 가장 큰 값을 반환하는 함수입니다.

 

maximum' [] = error "maximum of empty list"
maximum' [x] = x
maximum' (x:xs) = max x (maximum' xs)

result = maximum' [4, 5, 9, 2]
main = putStrLn (show result) -- ✅ 9

 

여기서 (x:xs) 는 배열의 요소를 분리하는 자주 사용되는 패턴입니다.

replicate 는 두 개의 인자 (n, m) 을 받아서 n을 m개 만큼 가지는 새로운 배열을 반환하는 함수입니다.

 

replicate' n m
  | m <= 0 = []
  | otherwise = n:replicate' n (m-1)

result = replicate' 2 5
main = putStrLn (show result) -- [2,2,2,2,2]

 

여기서 | 와 otherwise 는 Haskell 의 guard 문법입니다.

if 문과 유사한데, 각각의 조건을 좀 더 명확하게 파악할 수 있으며 패턴매칭과 궁합이 좋습니다.

take 는 두 개의 인자 x 와 arr 을 받아서 arr 에서 x 개 반큼 슬라이싱한 결과를 반환합니다.

 

take' n _
  | n <= 0 = []
take' _ [] = []
take' n (x:xs) = x : take' (n-1) xs

result = take' 2 [5, 4, 3, 2]
main = putStrLn (show result) -- [5,4]

 

reverse 는 배열을 뒤집는 함수입니다.

 

reverse' [] = []
reverse' (x:xs) = reverse' xs ++ [x]

result = reverse' [1, 2, 3, 4]
main = putStrLn (show result) -- [4, 3, 2, 1]

 

zip 은 두 배열을 받아서 각각의 index 로 매핑된 배열을 반환하는 함수입니다.

 

zip' _ [] = []
zip' [] _ = []
zip' (x:xs) (y:ys) = [(x, y)] ++ zip xs ys

result = zip' [1, 2, 3, 4] [5, 6, 7]
main = putStrLn (show result) -- [(1,5),(2,6),(3,7)]

 

elem 은 배열에 특정 요소가 존재하는지 판단하는 함수입니다.

 

elem' e [] = False
elem' e (x:xs)
  | e == x = True
  | otherwise = elem' e xs

result = elem' 3 [5, 6, 7]
main = putStrLn (show result) -- False

 

quicksort 는 배열을 정렬하는 알고리즘입니다.

Haskell 을 이용하면 명확하고 간결한 방식으로 이 알고리즘을 구현할 수 있습니다.

 

Quick Sort 의사코드

 

quick sort 를 짧게 설명하면, pivot 을 기준으로 작은 요소들을 모은 배열 A 와

큰 요소들만 모은 B 를 분리한 다음 이 세 그룹을 하나로 합친 뒤,

pivot 을 제외한 나머지 두 그룹에 대해서 동일한 방식으로 정렬을 해나가는 분할 정복 방식입니다.

edge-case 는 역시 빈 배열일 경우 정렬할 필요없이 [] 를 반환해주면 될 것입니다.

 

quicksort [] = []
quicksort (x:xs) =
  let smaller = quicksort [y | y <- xs, y < x]
      bigger = quicksort [y | y <- xs, y >= x]
  in smaller ++ [x] ++ bigger

result = quicksort [5, 1, 9, 4, 6, 7, 3]
main = putStrLn (show result) -- [1,3,4,5,6,7,9]

여기서 새롭게 등장하는 2가지 문법이 있습니다. 

list comprehension 는 배열을 인라인으로 생성하는 syntactic sugar 입니다.

let 과 in 은 함께 사용하여 특정 문맥에서 사용하는 지역 변수를 정의할 수 있습니다.

 

💡 list comprehension

이는 배열을 생성하는 하나의 방법입니다.

여기서는 generator 와 guard 들을 함께 사용하여 filter 등의 동작을 구현할 수도 있습니다.

[(i, j) | i <- [1,2], j <- [1,2]] -- [(1, 1), (1, 2), (2, 1), (2, 2)]

 

📌 재귀적으로 생각하기

지금까지 여러 예제들을 재귀함수로 구현해보면서 일정한 패턴이 있다는 것이 보일 것입니다.

1. 기저 케이스 생각해보기 (주로 이미 우리가 답을 알고 있는 케이스)
2. 문제를 작게 만들기
3. 작은 문제와 원래 문제 사이의 차이 줄이기

 

📌 참고자료

Substitution and Equational Reasoning