이제 기본적인 문법을 배웠으니 함수형 프로그래밍의 개념을 본격적으로 배워보도록 하자. 첫 타자는 꼬리재귀다.
1. 꼬리재귀
함수 호출을 할때, 호출자가 그 값을 수정하거나 조회하지 않으면 꼬리 호출이라고 한다.
함수의 모든 재귀적 호출이 꼬리 호출일때, 그 함수를 꼬리재귀적이라고 한다.
또는, 가장 마지막에 행해지는게 이 재귀 호출일때 그 함수는 꼬리재귀적이다.
다음은 리스트 안의 모든 숫자를 더하는 함수이다.
[1,2,3,4] 는 1::[2,3,4]로 볼 수도 있다는걸 염두에 두면서 코드를 읽어보자.
| sum (x::xs) = x + (sum xs)
이 함수는 꼬리재귀적이지 않다. 재귀호출이 끝난 후 x를 더하기 때문이다.
1강에서 팩토리얼 함수를 만든것과 비슷하게 accumulator변수를 사용해 함수의 인자에 값을 저장하는 방식을 사용했다.
| tsum (x::xs, acc) = tsum(xs, x + acc)
fun sum L = tsum(L, 0)
sum 함수는 꼬리재귀적이다. sum에서도, tsum 안에서도 재귀호출한 값을 수정하지 않기 때문이다.
꼬리재귀를 판단할 수 있는 또하나의 방법은 직접 실행시켜보면서 스택을 보는것이다.
첫번째 sum함수를 실행시켜보면 다음과 같이 피라미드 모양으로 스택이 늘어났다 줄어드는걸 볼 수 있다.
sum [3, 2, 1]
=> 3 + (sum [2, 1])
=> 3 + (2 + (sum [1]))
=> 3 + (2 + (1 + (sum [])))
=> 3 + (2 + (1 + (0)))
=> 3 + (2 + (1))
=> 3 + (3)
=> 6
이는 재귀호출이 많을경우 메모리 부족으로 이어지게 된다.
이번에는 두번째 sum함수의 호출을 보자.
sum [3, 2, 1]
=> tsum ([3, 2, 1], 0)
=> tsum ([2, 1], 3)
=> tsum ([1], 5)
=> tsum ([], 6)
=> 6
이렇게 꼬리재귀적 함수는 호출을 거듭할수록 스택이 늘어나지 않아서 메모리를 잡아먹지 않는다.
따라서 할수만 있다면 재귀함수는 꼬리재귀적으로 짜는게 좋다.
다만 이렇게 스택이 늘어나지 않으려면 컴파일러가 꼬리 재귀 최적화 (Tail Call Optimization)이라는 기법을 지원해야 한다.
SML을 포함해 함수형 언어들은 다 지원한다.
여기에 따르면 자바스크립트는 사파리에서만 지원한다고 한다.
꼬리재귀를 잘 이해했는지 확인하기 위해서 연습문제를 풀어보자.
문제 1) n번째 피보나치 수를 구하는 fib : int -> int 함수를 꼬리재귀적으로 만드시오. 보조함수를 사용해도 됨.
해답 1)
| fibHelper (n : int, a : int, b : int) : int = fibHelper(n - 1, a + b, a)
fun fib (n : int) : int = fibHelper(n, 1, 0)
문제 2) 다음은 주어진 리스트를 반전하는 함수다. 이 함수를 꼬리재귀적으로 다시 만드시오. 보조함수를 사용해도 됨.
@는 1강에서 잠시 설명했듯이 두 리스트를 연결하는 연산자이다.
해답 2)
| trev (x::xs, ys) = trev(xs, x::ys)
fun rev L = trev (L, [])
2. 매개변수 다형성
위 rev 함수의 타입은 무엇일까? int list -> int list? 그것도 아니면 string list -> string list?
정답은 "전부 다" 이다. 그냥 아무 리스트이기만 하면 rev는 동작한다.
이렇게 여러 타입을 인자로 받거나 값으로 내놓을 수 있는 함수를 다형적 함수 (polymorphic function)이라고 한다.
다형적 함수의 타입은 타입 변수를 이용해 나타낸다. 타입 변수는 여러 타입을 가질 수 있는 타입으로, 'a, 'b, 'c등을 이용해 나타낸다. 각각 알파, 베타, 감마라고 읽는다.
예시를 들면 저 rev 함수의 타입은 'a list -> 'a list이다. 'a 자리에 어느 타입이 들어와도 된다는 뜻이다.
자바 등에서 제네릭을 배웠다면 좀 비슷한 느낌을 받을 것이다.
그런데 타입변수가 여러개 필요한 상황에는 어떻게 할까?
다음은 임의의 길이가 2인 튜플의 리스트를 받아서 리스트의 길이를 구하는 함수이다.
| tupleListLength ((x, y)::xys) = 1 + tupleListLength xys
임의의 튜플 리스트를 받아서 int값을 만드니까 함수의 타입은 ('a * 'b) list -> int이다. 임의의 튜플을 표현하려면 두개의 타입 변수가 필요하기 때문이다.
이 함수의 타입은 무엇일까? 아무것도 정해지지 않았으나 SML 컴파일러는 자동으로 가장 일반적인 (most general) 타입을 유추해낸다.
'a -> 'b인가? 아니다. 인자와 리턴값의 타입이 같아야 하기 때문이다. 따라서 타입은 'a -> 'a이다.
타입을 유추하는게 지루해 보일수도 있겠지만 고차 함수를 설명하기 위해서 필요한 과정이다.
3. 사용자 정의 타입
잠시 문법으로 돌아가서, 리스트처럼 재귀적 타입을 직접 만드려면 어떻게 해야하는지 보자.
다음은 datatype 키워드를 사용해 사용자 정의 타입을 만드는 구문이다.
suit타입의 값은 Spades, Hearts, Diamonds, Clubs 중 하나라는 뜻이다.
datatype는 of 키워드를 사용하여 타입 인자를 받을 수 있다.
T option타입의 값은 NONE이거나 SOME x 이다. (x의 타입은 T)
예를 들어 SOME "hello" : string option이고 SOME 3 : int option이다.
option은 사실 SML에 이미 정의 되어있는 타입이며, option을 사용하면 NULL을 약간 흉내낼 수 있다.
다음은 option을 사용한 주어진 int의 역수를 구하는 함수이다. div는 정수나누기 연산자이다.
| reciprocal n = SOME (1 div n)
reciprocal을 호출해서 사용할때는 다음과 같이 1강에서 배운 case문을 써서 패턴매칭을 한다.
of NONE => A
| SOME r => B
이번에는 이진 트리 타입을 정의해보자. 코드를 작성하기 전에 이진 트리를 어떻게 정의할지 생각해보자.
모든 이진 트리는 다음 두가지 형태중 하나이다.
1) 빈 트리이거나
2) 맨 위 노드에 두 자식 이진트리가 연결되어있다
이걸 코드로 나타내면 다음과 같다.
Empty |
Node of 'a tree * 'a * 'a tree
예를 들어 Node(Empty, 3, Empty)는 노드가 하나뿐인 int tree 이다. 3은 그 노드 안에 담겨있는 데이터고.
위의 이진 트리를 표현하면 Node(Node(Empty, 1, Empty), 2, Node(Empty, 3, Empty))가 된다.
이렇게 정의한 이진트리의 높이를 구하는 height라는 함수를 만들어보자.
1강에서 리스트 함수 짤때 얘기한것 처럼, 재귀적으로 정의된 타입을 다룰때는 기본 타입일때와 복합 타입일때의 경우를 나누면 쉽다.
빈 트리의 경우를 먼저 생각해보자. 빈 트리의 높이는 0이다.
| height (Node (left, _, right)) =
빈 트리가 아니라면 트리는 Node('a tree, 'a, 'a tree)의 형태를 가지고 있다. 노드에 담겨있는 값은 높이를 구할때는 필요가 없으니 _를 써서 값을 저장하지 않았다.
| height (Node (left, _, right)) =
1 + max (height left, height right)
left의 높이와 right의 높이, 둘중 더 큰 높이에 1을 더한게 전체 높이가 된다.
연습문제로 주어진 이진 int tree의 모든 값을 더하는 함수 treesum : int tree -> int를 만들어보자.
해답)
| treesum Node(left, x, right) =
x + treesum left + treesum right
마지막으로 열린 질문을 하나 던지겠다. 저 height 함수는 현재 꼬리재귀적이지 않은데, 꼬리재귀로 만들 수 있을까?
긴글 읽느라 고맙고 다음에는 함수형 프로그래밍의 첫번째 난관인 고차 함수, 커링, 스테이징을 다뤄보도록 하겠다.
3강 : 커링, 스테이징, map, filter, fold
