4. OCaml - 재귀, 꼬리재귀와 고차함수

재귀와 고차함수

재귀와 고차함수를 사용함으로써 코드의 의도를 더 명확하게 표현하고 유지 관리가 쉬워지며 오류 가능성이 줄어든다. 즉 더 효율적이고 강력한 프로그래밍이 가능하다.

여기서 고차함수란 함수를 인자로 받거나 함수를 반환하는 함수를 의미한다. 예를 들어 map, filter, reduce와 같은 고차 함수들은 리스트나 배열을 처리할 때 반복되는 패턴의 코드를 간결하게 만들어 주고 재사용성과 모듈성을 향상시킨다.

 

재귀적 문제 해결 전략은 세 단계로 구분된다.

1. 분해 : 주어진 문제를 더 작고 동일한 구조를 가진 여러 부분 문제로 나눈다.

2. 해결 : 분해된 각 부분 문제를 재귀적으로 해결한다.

3. 통합 : 각 부분 문제의 해결 결과를 통합하여 전체 문제의 해결책을 도출한다.

 

 

아래는 예시들이다.

 

길이 구하기

let rec length l =
    match l with
    | [] -> 0
    | hd::tl -> 1 + length tl

리스트의 길이를 재는 위 함수로 예를 들어 보자.

리스트는 헤드와 테일로 나눌 수 있다. 테일의 길이를 구한다. 테일은 또한 []가 아니라면 헤드와 테일로 나눌 수 있다. 이는 []가 될 때까지 반복된다. 이 결과를 통합한다.

 

리스트 합치기

let rec append l1 l2 =
    match (l1, l2) with
    | ([], []) -> []
    | ([], l::t) -> l :: append [] t
    | (l::t, _) -> l :: append t l2;;

위 코드는 append를 구현한 것이다.

만약 앞 리스트가 비어있지 않다면, 앞 리스트의 헤드와 

만약 l1과 l2가 모두 빈 리스트 (가장 작은 경우) 에는 빈 리스트를 반환한다.

만약 l1만 빈 리스트라면, l2의 헤드와 append [] t를 합친다.

만약 l1이 빈 리스트가 아니라면, l1의 헤드와 append t l2를 합친다.

이 결과를 통합하면 list를 append할 수 있는 함수가 된다.

 

리스트 뒤집기

let rec reverse l =
  match l with
  | [] -> []
  | h::t -> reverse t @ [h];;

위 코드는 리스트 reverse를 구현한 것이다.

헤드를 뒤로 보내는 방식으로 구현했다.

 

n번째 요소 구하기

let rec nth l n =
  match l with
  | [] -> raise (Failure "list is too short")
  | hd::tl ->
    if n=0 then hd
    else nth tl (n-1);;

위 코드는 리스트 l에서 n번째 요소를 추출한다.

이 때, 마지막 줄에서 nth tl n-1 이라고 하면 연산자 우선순위에 의해 (nth tl n) - 1이 되므로 주의하자.

 

특정 요소 한 개 없애기

let rec remove_first a l =
  match l with
  | [] -> []
  | hd::tl ->
    if a==hd then tl
    else hd::remove_first a tl;;

리스트 l에서 맨 앞에 있는 요소 a를 제거한다.

 

정렬된 배열에 요소 적절히 끼워넣기

let rec insert a l =
  match l with
  | [] -> [a]
  | hd::tl ->
    if a <= hd then a::l
    else hd::insert a tl

리스트 l에 a를 삽입하되, l이 정렬리스트이도록 만든다.

 

삽입 정렬

let rec sort l =
  match l with
  | [] -> []
  | hd::tl -> insert hd (sort tl)

insert 함수를 사용하여, insertion sort를 구현할 수 있다.

 

 

꼬리 재귀

사실, OCaml에서는 꼬리재귀에 대해 최적화되어 있기 때문에 꼬리 재귀 호출이 추가 메모리를 소비하지 않는다.

 

이는 OCaml에서 재귀 호출 비용이 다른 언어와 다르기 때문인데,  C나 Java와 같은 언어에서는 void f() {f();} 와 같은 코드를 짜면 무한 재귀로 스택에 호출된 함수가 쌓여 오버플로우 된다.

 

그러나 OCaml 컴파일러는 f() → f()라는 꼬리 호출을 최적화해서 기존의 함수 호출 스택을 재사용한다.

따라서 무한 재귀더라도 이론상으로 무한히 실행되며 스택 오버플로우를 일으키지 않는다.

 

물론 무한히 실행될 뿐, 당연히 블로킹된다. 하지만 C에서 단순 재귀가 몇십만개 정도 쌓이면 segmentation fault를 마주할 수 있음을 생각해보자. 심지어 파이썬은 기본 재귀 깊이 제한이 1000이다. 물론 전술한 언어가 부족하다는 말은 절대 아니고, OCaml의 재귀 최적화 능력이 압도적이라는 뜻이다.

 

위에서 다룬 삽입 정렬을 꼬리 재귀로 표현하면 다음과 같다.

let rec insert_sort l =
  let rec insert a l' =
    match l' with
    | [] -> [a]
    | hd::tl ->
      if a <= hd then a::l'
      else hd::insert a tl
    in
    match l with
    | [] -> []
    | hd::tl -> insert hd (insert_sort tl)

insert 함수가 insert_sort 함수 안으로 들어왔을 뿐 전체적인 구조는 같다.

단, insert_sort 함수의 match l with ~ 구문은 insert 함수를 호출해야 하기 때문에 insert 함수의 로컬 변수 범위에 있어야 한다. 따라서 match 구문을 insert 함수의 지역으로 넣어주기 위해 in 키워드를 사용한다.

 

 

고차 함수

고차 함수는 함수를 인자로 받거나 함수를 반환하는 함수이다. 이는 추상화 능력과 코드 재사용성을 늘려준다.

map

let rec map f l =
  match l with
  | [] -> []
  | hd::tl -> (f hd) :: map f tl

리스트 l의 모든 요소에 함수 f를 적용시킨다.

만약 리스트의 모든 값에 1을 늘리는 함수, 요소를 2배로 늘리는 함수, 3제곱을 하는 함수가 각각 필요하다 했을 때, 이를 전부 새로 구현할 필요 없이 map 함수를 사용하여 구현할 수 있다.

 

fold

let rec fold f l a =
  match l with
  | [] -> a 
  | hd::tl -> f hd (fold f tl a)
  
(* example *)
# let prob l = fold (fun x y -> x*y) l 1;;
# prob [1;2;3;4]
- : 24

# let sum l = fold (fun x y -> x+y) l 0;;
# sum [1;2;3;4]
- : 10

sum, prod 등 리스트의 모든 값을 더하거나 곱할 때 쓰인다. 여기서 f는 함수, l은 리스트, a는 항등원, 최솟값이다.

 

fold 응용

(* not use fold *)
let rec length l =
  match l with
  | [] -> 0
  | hd::tl -> 1 + length tl

(* use fold *)
let rec length l = fold (fun x y -> 1+y) l 0;;

리스트의 길이를 구하는 작업을 fold를 이용해 구현할 수 있다.

 

(* not use fold *)
let rec reverse l =
  match l with
  | [] -> []
  | hd::tl -> (reverse tl) @ [hd]

(* use fold *)
let rec reverse l = fold (fun x y -> y@[x]) l [];;

리스트를 뒤집는 작업은 y와 x를 뒤집으면 된다.

 

 

(* not use fold *)
let rec is_all_pos l =
  match l with
  | [] -> true
  | hd::tl -> (hd > 0) && (is_all_pos tl)

(* use fold *)
let rec is_all_pos l = fold (fun x y -> (x>0) && y) l true;;

 

리스트의 모든 요소가 0보다 큰지 확인하려면, 모든 x에 대하여 0보다 크면 된다. 여기서 y는 x를 비교하고 남은 리스트이므로 and 연산을 취해준다.

 

 

함수 반환

let compose f g = fun x -> f(g(x))

compose 함수는 함수 f와 g를 받고 x → f(g(x)) 함수를 반환한다.

 

let square x = x * x
let inc x = x + 1

square 함수는 x를 제곱하는 함수, inc 함수는 x에 1을 더하는 함수이다.

compose 함수를 사용하여 square함수와 inc 함수를 합성해보자.

 

# (compose square inc) 6
- : 49

f(g(x))이므로, 뒤에 있는 함수인 inc가 먼저 실행된다. → 7

이어서 compose 함수가 실행된다. → 49

 

딕셔너리(맵) 구현

let empty_map = fun x -> raise (Failure "not exist!")

let add_map (k, v) map =
  fun x -> if k = x then v else map x;;

let m = add_map(0, "zero") empty_map;;
Printf.printf "%s " (m 0) (* zero가 출력된다 *)

let c_m = compose (add_map (1, "one")) (add_map (2, "two")) empty_map;;
Printf.printf "%s " (c_m 1) (* one이 출력된다 *)
Printf.printf "%s " (c_m 2) (* two가 출력된다 *)

 

위에서 구현한 compose를 사용한다.

먼저 empty_map은 키를 찾을 수 없을 때 에러를 발생시키기 위한 변수이다.

 

add_map (k, v) map은 함수를 반환한다. 반환되는 함수는 x를 입력받고, 만약 k와 같다면 v를 출력 (즉, key에 대한 value를 출력), 그렇지 않다면 map을 탐색한다.

m 변수는 empty_map에 (0, "zero")를 추가한 맵이다. 따라서 m 0을 출력하면 "zero"가 나오게 된다. 만약 없는 키, 예를 들어 m 1을 출력하면 add_map 함수의 else 구문으로 넘어가게 되고, map x를 호출한다. 이 때의 map은 empty_map이므로 에러가 발생한다.

 

c_m 변수는 (add_map (1, "one"))과 (add_map (2, "two"))를 compose의 인자로 넣고, 그로부터 반환된 함수에 empty_map을 넣어준 맵이다. 따라서 전체 구조는 다음과 같다.

g x = add_map (2, "two") x

f x = add_map (1, "one") x

여기서 x = empty_map

따라서 c_m = add_map(2, "two") (add_map(1, "one") empty_map) 이 된다.

 

c_m 2를 호출하면, 곧바로 "two" 가 반환된다.

c_m 1을 호출하면, 일단 처음 만나는 k값과 같지 않으므로 다음 맵인 add_map(1, "one")으로 넘어간다. 여기서는 k값과 같으므로 "one"이 반환된다.