15장: 알고리즘과 자료구조 (Algorithms and Data Structures)

이 장은 앞서 배운 모든 것을 실전에 적용하는 종합 실습입니다. 패턴 매칭, ADT, 재귀, 고차 함수, 모듈 — 지금까지 개별적으로 익혔던 도구들이 여기서 하나로 합쳐집니다.

함수형 프로그래밍으로 알고리즘을 구현하면 명령형 스타일과는 사뭇 다른 코드가 나옵니다. for 루프와 인덱스 변수 대신 재귀와 패턴 매칭이, 배열의 in-place 수정 대신 새로운 리스트의 생성이 중심이 됩니다. 처음에는 비효율적으로 보일 수 있지만, 코드의 정확성을 추론하기가 훨씬 쉽다는 장점이 있습니다. 각 함수가 입력을 받아 출력을 반환할 뿐 아무것도 변경하지 않으니까요.

먼저 FunLang에서 알고리즘을 작성할 때 알아두면 좋은 핵심 기능들을 정리합니다.

핵심 기능 정리

FunLang에서 알고리즘을 구현할 때 자주 사용하는 기능들입니다:

• 모듈 레벨 let rec: 재귀 함수를 최상위 선언으로 작성합니다. 표현식 내부의 let rec ... in 체인 대신, 각 함수를 독립된 선언으로 분리하면 가독성과 재사용성이 크게 향상됩니다.
• 리스트 범위: [1..100]으로 연속 정수 리스트를 간편하게 생성합니다.
• 상호 재귀: let rec f = ... and g = ...로 서로를 호출하는 함수를 정의합니다.
• Or 패턴: 패턴 매칭에서 여러 패턴을 하나로 묶을 수 있습니다.

모듈 레벨 let rec의 제약 사항을 기억하세요:

• 매개변수는 하나만 직접 받습니다: let rec f x = body
• 두 번째 매개변수부터는 클로저로 전달합니다: let rec f x = fun y -> body
• match 표현식은 한 줄 또는 들여쓰기 기반 여러 줄로 작성할 수 있습니다

이제 이 기능들을 활용한 알고리즘을 하나씩 살펴보겠습니다.

표준 리스트 함수

참고: map, filter, fold, length, reverse, append 등은 이제 Prelude에서 제공됩니다. 아래 예제에서는 구현 방법을 보여주기 위해 직접 정의하지만, 실제 프로그램에서는 Prelude 함수를 바로 사용할 수 있습니다.

함수형 프로그래밍에서 map, filter, fold는 가장 기본적인 도구입니다. 모듈 레벨에 선언하면 프로그램 전체에서 재사용할 수 있습니다.

Map

리스트의 각 원소에 함수를 적용하여 새 리스트를 만듭니다:

$ cat map.l3
let rec map f = fun xs ->
    match xs with
    | [] -> []
    | h :: t -> f h :: map f t

let result = map (fun x -> x * x) [1; 2; 3; 4; 5]

$ fn map.l3
[1; 4; 9; 16; 25]

map은 두 개의 매개변수를 받습니다. 첫 번째 f가 let rec 매개변수이고, 두 번째 xs는 fun xs -> ...를 통해 전달됩니다. 빈 리스트가 기저 사례이며, 비어 있지 않으면 head에 f를 적용하고 tail에 대해 재귀합니다.

Filter

조건을 만족하는 원소만 남깁니다:

$ cat filter.l3
let rec filter pred = fun xs ->
    match xs with
    | [] -> []
    | h :: t -> if pred h then h :: filter pred t else filter pred t

let result = filter (fun x -> x % 2 = 0) [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]

$ fn filter.l3
[2; 4; 6; 8; 10]

x % 2 = 0은 % (모듈로) 연산자로 짝수를 판별합니다.

Fold (왼쪽 폴드)

왼쪽 폴드는 리스트를 하나의 값으로 축약합니다. 이항 함수 f, 초기 누적자 acc, 리스트 xs 세 개의 매개변수를 받습니다:

$ cat fold.l3
let rec fold f = fun acc -> fun xs ->
    match xs with
    | [] -> acc
    | h :: t -> fold f (f acc h) t

let result = fold (fun acc -> fun x -> acc + x * x) 0 [1; 2; 3; 4; 5]

$ fn fold.l3
55

세 개의 매개변수가 중첩 클로저로 전달됩니다: f가 let rec 매개변수, acc가 첫 번째 fun, xs가 두 번째 fun입니다. 계산 과정은 0 + 1 + 4 + 9 + 16 + 25 = 55입니다.

Prelude를 활용한 간결한 코드

Prelude 함수를 사용하면 알고리즘을 더 간결하게 작성할 수 있습니다:

$ cat sieve_prelude.l3
let rec sieve xs =
    match xs with
    | [] -> []
    | p :: rest -> p :: sieve (filter (fun n -> n % p <> 0) rest)

let result = sieve [2..50]

$ fn sieve_prelude.l3
[2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47]

filter는 Prelude에서 제공되므로 재정의할 필요 없이, sieve 함수만 작성하면 에라토스테네스의 체를 구현할 수 있습니다.

수론

팩토리얼

가장 기본적인 재귀 알고리즘입니다. 모듈 레벨 let rec으로 깔끔하게 표현됩니다:

$ cat factorial.l3
let rec fact n = if n <= 1 then 1 else n * fact (n - 1)

let result = fact 10

$ fn factorial.l3
3628800

fact 10은 10 * 9 * 8 * … * 1 = 3,628,800을 계산합니다. 함수 정의와 호출이 분리되어 읽기 좋습니다.

피보나치 수열

단순 재귀 피보나치를 리스트 범위와 map을 결합하여 수열 전체를 출력합니다:

$ cat fibonacci.l3
let rec fib n = if n <= 1 then n else fib (n - 1) + fib (n - 2)
let rec map f = fun xs ->
    match xs with
    | [] -> []
    | h :: t -> f h :: map f t

let result = map fib [0..15]

$ fn fibonacci.l3
[0; 1; 1; 2; 3; 5; 8; 13; 21; 34; 55; 89; 144; 233; 377; 610]

[0..15]는 0부터 15까지 16개의 정수 리스트를 생성합니다. map fib [0..15]는 각 인덱스에 대한 피보나치 값을 계산합니다.

GCD와 LCM

유클리드 알고리즘으로 최대공약수를 구하고, 이를 이용해 최소공배수를 유도합니다:

$ cat gcd_lcm.l3
let rec gcd a = fun b ->
    if b = 0 then a else gcd b (a % b)

let lcm a = fun b ->
    a / gcd a b * b

let result = (gcd 48 36, lcm 12 18)

$ fn gcd_lcm.l3
(12, 36)

gcd 48 36의 축약: gcd 48 36 -> gcd 36 12 -> gcd 12 0 -> 12. lcm 12 18은 12 / gcd(12,18) * 18 = 12 / 6 * 18 = 36입니다.

a % b는 나머지(모듈로) 연산자입니다. lcm은 재귀가 아니므로 let rec 없이 일반 let으로 정의합니다.

서로소 (Coprimes)

GCD와 리스트 범위를 결합하면 주어진 수와 서로소인 수를 구할 수 있습니다:

$ cat coprimes.l3
let rec gcd a = fun b ->
    if b = 0 then a else gcd b (a % b)
let rec filter pred = fun xs ->
    match xs with
    | [] -> []
    | h :: t -> if pred h then h :: filter pred t else filter pred t

let coprimes n = filter (fun k -> gcd n k = 1) [1..n]
let result = coprimes 12

$ fn coprimes.l3
[1; 5; 7; 11]

[1..12] 중에서 12와 GCD가 1인 수만 남깁니다. 이것이 오일러 토션트 함수 phi(12) = 4의 구체적인 원소들입니다. 리스트 범위 덕분에 [1..n]으로 간결하게 후보를 생성할 수 있습니다.

소수 판별 (isPrime)

주어진 범위에서 소수를 걸러냅니다:

$ cat is_prime.l3
let rec filter pred = fun xs ->
    match xs with
    | [] -> []
    | h :: t -> if pred h then h :: filter pred t else filter pred t
let rec checkPrime n = fun d -> if d * d > n then true else if n % d = 0 then false else checkPrime n (d + 1)
let isPrime n = if n < 2 then false else checkPrime n 2

let result = filter (fun n -> isPrime n) [2..50]

$ fn is_prime.l3
[2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47]

checkPrime n d는 2부터 sqrt(n)까지 나눠보며 소수를 판별합니다. isPrime은 비재귀 래퍼로, 2 미만인 경우를 먼저 걸러냅니다. [2..50]에서 소수만 필터링하여 50 이하의 모든 소수를 구합니다.

거듭제곱

반복 곱셈으로 base^exp를 계산합니다:

$ cat power.l3
let rec power base = fun exp ->
    if exp = 0 then 1 else base * power base (exp - 1)

let result = power 2 10

$ fn power.l3
1024

power 2 10은 2^10 = 1024를 계산합니다.

정렬 알고리즘

정렬은 알고리즘을 비교하기 좋은 주제입니다. 모듈 레벨 let rec 덕분에 각 헬퍼 함수가 독립 선언이 되어 구조가 명확합니다.

삽입 정렬

각 원소를 정렬된 리스트의 올바른 위치에 삽입하여 정렬합니다:

$ cat insertion_sort.l3
let rec insert x = fun xs ->
    match xs with
    | [] -> x :: []
    | h :: t -> if x <= h then x :: h :: t else h :: insert x t

let rec sort xs =
    match xs with
    | [] -> []
    | h :: t -> insert h (sort t)

let result = sort [5; 3; 8; 1; 9; 2; 7; 4; 6]

$ fn insertion_sort.l3
[1; 2; 3; 4; 5; 6; 7; 8; 9]

insert와 sort가 각각 독립된 최상위 함수입니다. insert는 정렬된 리스트에서 올바른 위치를 찾을 때까지 순회하고, sort는 tail을 재귀적으로 정렬한 후 head를 삽입합니다. 최악의 경우 O(n^2)이지만 구현이 단순하고 안정적(stable)입니다.

퀵정렬

피벗을 기준으로 분할하고, 각 부분을 재귀 정렬한 후 합칩니다:

$ cat quicksort.l3
let rec filter pred = fun xs ->
    match xs with
    | [] -> []
    | h :: t -> if pred h then h :: filter pred t else filter pred t

let rec append xs = fun ys ->
    match xs with
    | [] -> ys
    | h :: t -> h :: append t ys

let rec qsort xs =
    match xs with
    | [] -> []
    | pivot :: rest ->
        let lo = filter (fun x -> x < pivot) rest
        in let hi = filter (fun x -> x >= pivot) rest
        in append (qsort lo) (pivot :: qsort hi)

let result = qsort [5; 3; 8; 1; 9; 2; 7; 4; 6]

$ fn quicksort.l3
[1; 2; 3; 4; 5; 6; 7; 8; 9]

filter, append, qsort 세 함수가 각각 독립 선언입니다. 피벗은 리스트의 head를 사용합니다. filter로 피벗보다 작은 원소(lo)와 크거나 같은 원소(hi)를 분리한 후, 정렬된 결과를 append (qsort lo) (pivot :: qsort hi)로 조합합니다.

Prelude ++ 연산자를 사용하면 append를 재정의할 필요가 없어 더 간결합니다:

$ cat qsort_prelude.l3
let rec qsort xs =
    match xs with
    | [] -> []
    | p :: rest ->
        qsort (filter (fun x -> x < p) rest) ++ [p] ++ qsort (filter (fun x -> x >= p) rest)

let result = qsort [5; 3; 8; 1; 9; 2; 7]

$ fn qsort_prelude.l3
[1; 2; 3; 5; 7; 8; 9]

병합 정렬

리스트를 반으로 나누고, 각 반쪽을 정렬한 후 병합합니다. 여러 헬퍼 함수가 필요한 알고리즘에서 모듈 레벨 선언의 장점이 특히 드러납니다:

$ cat merge_sort.l3
let rec length xs =
    match xs with
    | [] -> 0
    | _ :: t -> 1 + length t
let rec take n = fun xs ->
    if n = 0 then []
    else match xs with
         | [] -> []
         | h :: t -> h :: take (n - 1) t
let rec drop n = fun xs ->
    if n = 0 then xs
    else match xs with
         | [] -> []
         | _ :: t -> drop (n - 1) t
// 두 정렬된 리스트의 head를 비교하며 병합
let rec merge xs = fun ys ->
    match xs with
    | [] -> ys
    | x :: xt ->
        match ys with
        | [] -> xs
        | y :: yt -> if x <= y then x :: merge xt (y :: yt) else y :: merge (x :: xt) yt
// 리스트를 반으로 나눠 각각 정렬 후 병합 (O(n log n))
let rec msort xs =
    let len = length xs
    in if len <= 1 then xs
    else let mid = len / 2
         in merge (msort (take mid xs)) (msort (drop mid xs))

let result = msort [5; 3; 8; 1; 9; 2; 7; 4; 6]

$ fn merge_sort.l3
[1; 2; 3; 4; 5; 6; 7; 8; 9]

다섯 개의 함수가 각각 독립된 최상위 선언입니다. 각 함수를 독립적으로 읽고 이해할 수 있습니다.

take과 drop이 리스트를 중간점에서 분할하고, merge가 두 정렬된 리스트의 head를 비교하며 교차 배치합니다. O(n log n)이 보장됩니다.

트리 자료구조

이진 탐색 트리와 트리 정렬

대수적 데이터 타입으로 이진 트리를 정의하고, 삽입/구축/순회를 구현하여 트리 기반 정렬을 만듭니다:

$ cat tree_sort.l3
type Tree =
    | Leaf
    | Node of Tree * int * Tree

// BST 삽입: 값을 비교하여 왼쪽 또는 오른쪽 하위 트리에 재귀 삽입
let rec treeInsert x = fun t ->
    match t with
    | Leaf -> Node (Leaf, x, Leaf)
    | Node (l, v, r) -> if x <= v then Node (treeInsert x l, v, r) else Node (l, v, treeInsert x r)
let rec buildTree xs =
    match xs with
    | [] -> Leaf
    | h :: t -> treeInsert h (buildTree t)
let rec append xs = fun ys ->
    match xs with
    | [] -> ys
    | h :: t -> h :: append t ys
let rec inorder t =
    match t with
    | Leaf -> []
    | Node (l, v, r) -> append (inorder l) (v :: inorder r)

let result = inorder (buildTree [5; 3; 8; 1; 9; 2; 7])

$ fn tree_sort.l3
[1; 2; 3; 5; 7; 8; 9]

Tree 타입은 두 생성자를 가진 대수적 데이터 타입입니다: Leaf(빈 노드)와 Node(왼쪽 하위 트리, 값, 오른쪽 하위 트리). treeInsert는 노드 값과 비교하여 왼쪽 또는 오른쪽으로 재귀하며 BST 성질을 유지합니다. buildTree로 리스트를 트리로 변환하고, inorder 중위 순회로 정렬된 리스트를 추출합니다.

페아노 자연수

자연수를 대수적 타입으로 표현하고, 구조적 재귀로 덧셈과 곱셈을 정의합니다. 수학의 기초를 코드로 직접 표현하는 예제입니다:

$ cat peano.l3
type Nat =
    | Zero
    | Succ of Nat

let rec toInt n =
    match n with
    | Zero -> 0
    | Succ p -> 1 + toInt p
let rec add a = fun b ->
    match a with
    | Zero -> b
    | Succ p -> Succ (add p b)
let rec mul a = fun b ->
    match a with
    | Zero -> Zero
    | Succ p -> add b (mul p b)

let three = Succ (Succ (Succ Zero))
let four = Succ (Succ (Succ (Succ Zero)))
let result = toInt (mul three four)

$ fn peano.l3
12

add는 a에서 Succ를 하나씩 벗기고 결과를 감쌉니다: add (Succ (Succ Zero)) b = Succ (Succ b). mul은 반복 덧셈을 사용합니다: mul (Succ (Succ Zero)) b = add b (add b Zero).

3 * 4 = 12를 toInt로 검증합니다. 모듈 레벨 선언 덕분에 toInt, add, mul이 각각 독립된 함수로 깔끔하게 정의됩니다.

응용 알고리즘

리스트 범위, 상호 재귀, or 패턴 등을 활용하는 알고리즘입니다.

에라토스테네스의 체

고대 그리스의 소수 알고리즘입니다. 리스트 범위 [2..50]으로 후보를 생성하고, 가장 작은 수의 배수를 반복적으로 제거합니다:

$ cat sieve.l3
let rec filter pred = fun xs ->
    match xs with
    | [] -> []
    | h :: t -> if pred h then h :: filter pred t else filter pred t
let rec sieve xs =
    match xs with
    | [] -> []
    | p :: rest -> p :: sieve (filter (fun n -> n % p <> 0) rest)

let result = sieve [2..50]

$ fn sieve.l3
[2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47]

[2..50]이 2부터 50까지의 리스트를 생성합니다. sieve는 리스트의 첫 원소 p를 소수로 확정하고, 나머지에서 p의 배수를 filter로 제거한 후 재귀합니다. n % p <> 0은 % 연산자로 n이 p의 배수가 아닌지 검사합니다.

이 알고리즘은 리스트 범위 없이는 후보 리스트를 수동으로 나열해야 했을 것입니다. [2..50] 한 표현으로 깔끔하게 해결됩니다.

Collatz 수열

콜라츠 추측은 어떤 양의 정수에서 시작하든 “짝수면 반으로, 홀수면 3n+1“을 반복하면 결국 1에 도달한다는 것입니다. 수열을 추적합니다:

$ cat collatz.l3
let rec collatz n = fun acc ->
    if n = 1 then n :: acc else if n % 2 = 0 then collatz (n / 2) (n :: acc) else collatz (3 * n + 1) (n :: acc)
let rec rev acc = fun xs ->
    match xs with
    | [] -> acc
    | h :: t -> rev (h :: acc) t

// 수열의 길이만 확인 (27에서 시작하면 112단계를 거쳐 1에 도달)
let seq = rev [] (collatz 27 [])
let result = length seq

$ fn collatz.l3
112

collatz는 꼬리 재귀 함수로, 누적자 acc에 각 단계의 값을 기록합니다. 결과가 역순으로 쌓이므로 rev로 뒤집습니다. 27에서 시작하면 112단계를 거쳐 1에 도달합니다. n % 2 = 0으로 짝수/홀수를 판별합니다.

FizzBuzz

프로그래밍 면접의 고전 문제입니다. 리스트 범위와 map을 결합합니다:

$ cat fizzbuzz.l3
let rec map f = fun xs ->
    match xs with
    | [] -> []
    | h :: t -> f h :: map f t

let fizzbuzz n =
    let r3 = n % 3
    let r5 = n % 5
    match (r3, r5) with
    | (0, 0) -> "FizzBuzz"
    | (0, _) -> "Fizz"
    | (_, 0) -> "Buzz"
    | _ -> to_string n

let result = map fizzbuzz [1..20]

$ fn fizzbuzz.l3
["1"; "2"; "Fizz"; "4"; "Buzz"; "Fizz"; "7"; "8"; "Fizz"; "Buzz"; "11"; "Fizz"; "13"; "14"; "FizzBuzz"; "16"; "17"; "Fizz"; "19"; "Buzz"]

fizzbuzz는 % 연산자로 3과 5의 나머지를 구하고 튜플로 만들어 패턴 매칭합니다. (0, 0)이면 둘 다 나누어지므로 “FizzBuzz”, (0, _)이면 3만 나누어지므로 “Fizz”, (_, 0)이면 5만 나누어지므로 “Buzz”, 나머지는 숫자 자체를 문자열로 변환합니다. [1..20]으로 1부터 20까지 범위를 생성하고 map fizzbuzz로 변환합니다.

상태 머신 (상호 재귀)

let rec ... and ... 구문은 서로를 호출하는 함수를 정의할 수 있게 합니다. 상태 머신은 상호 재귀의 대표적인 활용 사례입니다:

$ cat state_machine.l3
let rec stateA xs =
    match xs with
    | [] -> "ended in A"
    | 0 :: rest -> stateB rest
    | _ :: rest -> stateA rest
and stateB xs =
    match xs with
    | [] -> "ended in B"
    | 1 :: rest -> stateA rest
    | _ :: rest -> stateB rest

let r1 = stateA [1; 0; 1; 0]
let r2 = stateA [1; 0; 0]
let result = (r1, r2)

$ fn state_machine.l3
(ended in B, ended in B)

두 상태 A, B 사이를 전이하는 간단한 오토마톤입니다:

• 상태 A: 입력이 0이면 상태 B로 전이, 그 외에는 A에 머무름
• 상태 B: 입력이 1이면 상태 A로 전이, 그 외에는 B에 머무름

let rec stateA ... and stateB ...로 두 함수가 서로를 호출할 수 있습니다.

첫 번째 입력 [1; 0; 1; 0]은 A -> A -> B -> A -> B 경로를 따라 상태 B에서 끝납니다. 두 번째 [1; 0; 0]은 A -> A -> B -> B로 역시 상태 B에서 끝납니다.

요약

이 장에서 사용한 핵심 기능:

• 모듈 레벨 let rec: 재귀 함수를 최상위 선언으로 작성합니다. 각 함수가 독립적이어서 읽기 쉽고 재사용하기 좋습니다.
• 리스트 범위: [1..n]으로 연속 정수 리스트를 생성합니다. 에라토스테네스의 체, 소수 필터링, FizzBuzz 등에서 활용됩니다.
• 상호 재귀: let rec f = ... and g = ...로 서로를 호출하는 함수를 정의합니다. 상태 머신, 홀수/짝수 판별기 등에서 활용됩니다.
• 대수적 데이터 타입은 재귀 함수와 자연스럽게 결합되어 트리, 수식 언어, 사용자 정의 수 타입에 활용됩니다.