3장: 리스트와 튜플 (Lists and Tuples)

데이터를 다루다 보면 여러 값을 함께 묶어야 할 순간이 반드시 옵니다. FunLang는 두 가지 기본 컬렉션을 제공합니다: 리스트(list)와 튜플(tuple). 얼핏 비슷해 보이지만 설계 철학이 다릅니다. 리스트는 “같은 종류의 값들을 가변 개수로”, 튜플은 “다른 종류의 값들을 고정 개수로” 묶는 데 쓰입니다. 이 장에서는 두 컬렉션의 특성과 활용 방법을 살펴봅니다.

리스트 기초

리스트는 함수형 언어의 가장 기본적인 자료구조입니다. Haskell, OCaml, F# 모두 리스트를 핵심 자료구조로 삼고 있으며, FunLang도 마찬가지입니다.

리스트는 순서가 있는 동질적(homogeneous) 컬렉션입니다:

fn> [1; 2; 3]
[1; 2; 3]

fn> []
[]

“동질적(homogeneous)“이라는 말은 리스트 안의 모든 원소가 같은 타입이어야 한다는 뜻입니다. [1; "hello"; true]처럼 타입이 섞인 리스트는 컴파일 에러가 됩니다. 처음에는 제약처럼 느껴지지만, 이 덕분에 리스트를 처리하는 함수를 안전하게 작성할 수 있습니다 – 원소 타입을 미리 알 수 있으니까요.

cons 연산자 ::는 요소를 앞에 추가합니다:

fn> 1 :: [2; 3]
[1; 2; 3]

fn> 1 :: 2 :: 3 :: []
[1; 2; 3]

:: 연산자는 함수형 언어 리스트의 핵심입니다. OCaml, Haskell에서도 같은 역할을 하며, “cons“라고 읽습니다. 1 :: [2; 3]은 “1과 [2; 3]을 연결(cons)한다“는 뜻입니다. 1 :: 2 :: 3 :: []처럼 오른쪽에서 왼쪽으로 연결해 나가는 방식으로 리스트를 구성할 수 있습니다. 패턴 매칭에서 x :: rest 형태로 리스트를 분해할 때도 이 연산자가 활용됩니다.

중요한 점은 :: 가 새 리스트를 만드는 것이지 기존 리스트를 변경하지 않는다는 점입니다. FunLang의 리스트는 불변(immutable)입니다. 원소를 앞에 추가하는 것은 O(1) 연산이고, 리스트를 뒤에서 추가하는 것은 O(n)입니다 – 이 특성이 재귀적 리스트 처리 패턴의 기반이 됩니다.

리스트 범위 (List Ranges)

연속된 숫자 리스트를 만들어야 할 때마다 [1; 2; 3; 4; 5; ...]처럼 일일이 쓰는 것은 번거롭습니다. 범위 구문이 이를 해결합니다.

[start..stop] 구문으로 정수 리스트를 생성할 수 있습니다:

fn> [1..5]
[1; 2; 3; 4; 5]

fn> [1..10]
[1; 2; 3; 4; 5; 6; 7; 8; 9; 10]

스텝(증가값)을 지정할 수도 있습니다. [start..step..stop] 형태입니다:

fn> [1..2..10]
[1; 3; 5; 7; 9]

fn> [0..5..20]
[0; 5; 10; 15; 20]

F#의 [1..2..10] 문법과 동일합니다. Python의 range(1, 11, 2)와 비교하면 더 자연스럽게 읽힙니다. 스텝을 생략하면 기본값은 1입니다.

stop이 start보다 작으면 빈 리스트를 반환합니다 (F# 동작과 동일):

fn> [5..1]
[]

단일 원소 범위:

fn> [3..3]
[3]

[5..1]이 에러가 아닌 빈 리스트를 반환한다는 점을 기억하세요. 이 동작이 유용할 때도 있고 예상치 못한 빈 리스트로 버그가 생길 수도 있습니다. 변수로 범위를 만들 때는 start <= stop인지 확인하는 습관을 들이세요.

범위는 파이프 연산자와 함께 유용합니다:

$ cat range_sum.l3
let result =
    let rec fold f = fun acc -> fun xs ->
        match xs with
        | [] -> acc
        | h :: t -> fold f (f acc h) t
    fold (fun acc -> fun x -> acc + x) 0 [1..100]

$ fn range_sum.l3
5050

1부터 100까지의 합을 구하는 고전적인 예제입니다. [1..100]으로 100개 원소의 리스트를 만들고, fold로 누적 합산합니다. Gauss가 초등학생 때 암산으로 계산했다는 바로 그 5050입니다.

참고: 범위는 정수(int)만 지원합니다. 스텝이 0이면 런타임 에러가 발생합니다.

튜플 (Tuples)

리스트가 “여러 개의 같은 것“을 담는다면, 튜플은 “고정 개수의 다른 것“을 담습니다. 이름, 나이, 활성화 여부처럼 서로 다른 타입의 값들을 하나로 묶을 때 튜플을 씁니다.

튜플은 고정 크기의 이질적(heterogeneous) 컬렉션입니다:

fn> (1, "hello")
(1, "hello")

fn> (1, "hello", true)
(1, "hello", true)

(1, "hello")는 int * string 타입, (1, "hello", true)는 int * string * bool 타입입니다. 타입 표기에서 *를 쓰는 것은 수학의 곱집합(Cartesian product)에서 왔습니다 – int * string은 정수와 문자열의 가능한 모든 조합의 집합입니다.

패턴 바인딩으로 튜플을 분해할 수 있습니다:

fn> let (x, y) = (1, 2) in x + y
3

fn> let (a, b, c) = (1, 2, 3) in a + b + c
6

튜플 분해(destructuring)는 매우 자주 쓰이는 패턴입니다. fst, snd 같은 접근 함수 없이 바로 이름을 붙여 사용할 수 있어 코드가 훨씬 명확해집니다. 함수에서 여러 값을 반환해야 할 때 튜플을 쓰고, 받는 쪽에서 즉시 분해하는 패턴이 FunLang에서 아주 흔합니다.

함수가 여러 값을 반환하는 것처럼 보이게 하는 관용적인 방법이 바로 튜플입니다. 실제로는 하나의 튜플 값을 반환하지만, 호출자에서 분해하면 여러 값을 받는 것처럼 느껴집니다.

유닛 (Unit)

1장에서 유닛 타입을 소개했지만, 튜플의 맥락에서 다시 보면 더 명확합니다. 유닛은 사실 원소가 0개인 튜플입니다.

유닛 타입 ()는 “값 없음“을 나타냅니다:

fn> ()
()

()를 빈 튜플로 생각하면 이해가 쉽습니다. (1, 2)는 원소 두 개짜리 튜플, (1,)은 원소 하나짜리 튜플, ()는 원소 없는 튜플. 이 시각으로 보면 유닛이 타입 시스템 안에서 일관되게 취급되는 이유가 납득됩니다.

리스트와 튜플 조합

리스트와 튜플은 자유롭게 조합할 수 있습니다. 실제 프로그램에서는 이런 조합이 자주 등장합니다.

튜플의 리스트:

fn> [(1, "a"); (2, "b")]
[(1, "a"); (2, "b")]

이 패턴은 키-값 쌍의 목록, 좌표 목록, 레코드 목록 등 다양한 용도로 쓰입니다. 데이터베이스의 행(row)을 튜플로, 테이블 전체를 리스트로 표현하는 방식입니다. 4장에서 배우는 패턴 매칭과 결합하면 이런 구조를 우아하게 처리할 수 있습니다.

리스트 함수

리스트를 다루는 핵심 도구들입니다. Prelude에서 제공하는 함수들을 먼저 살펴보고, 필요할 때 직접 작성하는 방법도 알아봅니다.

Prelude 함수 사용하기

map, filter, fold, length, reverse, append 등 자주 사용하는 리스트 함수는 Prelude 표준 라이브러리에서 제공됩니다. 별도의 정의 없이 바로 사용할 수 있습니다. 각 함수의 상세한 설명과 Option/Result 타입은 9장: Prelude 표준 라이브러리에서 다룹니다. 여기서는 리스트 처리에 필요한 핵심만 소개합니다:

fn> map (fun x -> x * 2) [1; 2; 3]
[2; 4; 6]

fn> filter (fun x -> x > 2) [1; 2; 3; 4; 5]
[3; 4; 5]

fn> fold (fun acc -> fun x -> acc + x) 0 [1..5]
15

fn> length [1; 2; 3; 4]
4

fn> append [1; 2] [3; 4]
[1; 2; 3; 4]

이 세 함수 – map, filter, fold – 는 함수형 프로그래밍의 삼위일체라고 할 수 있습니다. Haskell, F#, Python의 functools, JavaScript의 Array 메서드 모두 이 패턴을 따릅니다.

map은 변환: 리스트의 모든 원소에 함수를 적용해 새 리스트를 만듭니다. filter는 선택: 조건을 만족하는 원소만 남깁니다. fold는 축약: 리스트 전체를 하나의 값으로 압축합니다. 이 세 함수를 잘 조합하면 대부분의 리스트 처리 문제를 해결할 수 있습니다.

fold의 시그니처가 낯설 수 있습니다. fun acc -> fun x -> acc + x처럼 누적값과 현재 원소를 각각 인자로 받는 커링된 함수를 넘기는 것이 FunLang 스타일입니다. 초기값(0)과 리스트를 마지막에 넘깁니다.

++ 연산자는 append의 별칭입니다. 더 자연스러운 중위 표기를 제공합니다:

fn> [1; 2] ++ [3; 4]
[1; 2; 3; 4]

fn> [1..3] ++ [10..12]
[1; 2; 3; 10; 11; 12]

(++)를 고차 함수로도 사용할 수 있습니다:

fn> fold (++) [] [[1; 2]; [3]; [4; 5]]
[1; 2; 3; 4; 5]

fold (++) [] [[1;2]; [3]; [4;5]]는 리스트의 리스트를 하나로 평탄화(flatten)합니다. (++)를 괄호로 감싸면 중위 연산자를 일반 함수처럼 쓸 수 있는 것이 포인트입니다. 이런 방식으로 연산자를 fold에 직접 넘길 수 있습니다.

append(혹은 ++)는 O(n) 연산임을 기억하세요. 왼쪽 리스트의 모든 원소를 복사해야 합니다. 리스트 앞에 추가하는 :: 는 O(1)입니다. 리스트를 쌓아나가는 알고리즘을 작성할 때 ++ 대신 :: 로 앞에 추가하고 마지막에 reverse하는 것이 더 효율적인 이유입니다.

직접 재귀 함수 작성하기

Prelude에 없는 동작이 필요하면 let rec으로 직접 재귀 함수를 작성할 수 있습니다. let rec는 단일 매개변수만 지원하므로, 추가 상태를 전달하려면 클로저(closure)를 사용하세요.

합계:

$ cat sum.l3
let rec sum xs =
    match xs with
    | [] -> 0
    | x :: rest -> x + sum rest

let result = sum [1; 2; 3; 4; 5]
let _ = println (to_string result)

$ fn sum.l3
15

각 요소를 10배로:

$ cat map10.l3
let rec go xs =
    match xs with
    | [] -> []
    | x :: rest -> x * 10 :: go rest

let result = go [1; 2; 3]
let _ = println (to_string result)

$ fn map10.l3
[10; 20; 30]

이 두 예제는 리스트 재귀의 기본 패턴을 잘 보여줍니다. 빈 리스트([])가 기저 사례(base case)이고, x :: rest로 분해해 머리(head) x를 처리한 뒤 꼬리(tail) rest에 재귀 호출하는 것이 귀납 사례(inductive case)입니다. Haskell을 비롯한 모든 함수형 언어에서 리스트 재귀는 이 구조를 따릅니다.

sum은 fold (fun acc -> fun x -> acc + x) 0으로, go는 map (fun x -> x * 10)으로 표현할 수 있습니다. 그렇다면 언제 직접 재귀를 써야 할까요? Prelude에 없는 복잡한 변환이 필요하거나, 여러 상태를 동시에 추적해야 하거나, 특수한 종료 조건이 있을 때입니다. 먼저 map/filter/fold로 해결할 수 있는지 확인하고, 안 되면 직접 작성하는 것이 좋은 순서입니다.

리스트 컴프리헨션 (List Comprehensions)

리스트를 변환하거나 생성할 때, map을 호출하는 대신 컴프리헨션 구문으로 더 직관적으로 표현할 수 있습니다. Python의 리스트 컴프리헨션과 비슷한 개념입니다.

컬렉션에서 생성

[for x in collection -> expr] 구문으로 컬렉션의 각 원소를 변환한 새 리스트를 만듭니다:

$ cat comp_basic.l3
let doubled = [for x in [1;2;3] -> x * 2]
let _ = println (to_string doubled)
let strs = [for s in ["a";"b";"c"] -> s ^^ "!"]
let _ = println (to_string strs)

$ fn comp_basic.l3
[2; 4; 6]
["a!"; "b!"; "c!"]
()

[for x in [1;2;3] -> x * 2]는 map (fun x -> x * 2) [1;2;3]와 같은 결과를 반환합니다. 어떤 것을 쓸지는 취향이지만, 변환 표현식이 복잡할 때는 컴프리헨션이 더 읽기 쉬운 경우가 많습니다.

범위에서 생성

[for i in start..stop -> expr] 구문으로 정수 범위를 순회하며 리스트를 생성합니다:

$ cat comp_range.l3
let squares = [for i in 0..4 -> i * i]
let _ = println (to_string squares)
let tens = [for i in 1..3 -> i * 10]
let _ = println (to_string tens)

$ fn comp_range.l3
[0; 1; 4; 9; 16]
[10; 20; 30]
()

0..4는 0, 1, 2, 3, 4를 순서대로 생성합니다. 리스트 범위 [0..4]와 동일한 범위이지만, 컴프리헨션에서는 각 값에 표현식을 적용하여 새 리스트를 만듭니다.

엣지 케이스

빈 컬렉션이나 단일 원소 컬렉션도 정상 동작합니다:

$ cat comp_edge.l3
let empty = [for x in [] -> x * 2]
let _ = println (to_string empty)
let single = [for x in [42] -> x + 1]
let _ = println (to_string single)
let nested = [for x in [1;2;3] -> to_string (x * x)]
let _ = println (to_string nested)

$ fn comp_edge.l3
[]
[43]
["1"; "4"; "9"]
()

화살표 -> 오른쪽에는 임의의 표현식을 쓸 수 있으므로, to_string이나 다른 함수를 호출하는 것도 자연스럽습니다.

리스트 패턴 매칭 (Pattern Matching on Lists)

4장 미리보기 – 리스트 패턴을 사용한 match:

fn> match [1; 2; 3] with | [] -> "empty" | x :: _ -> to_string x
"1"

중첩 구조 분해(nested destructuring):

fn> match [1; 2; 3] with | a :: b :: _ -> a + b | _ -> 0
3

패턴 매칭은 FunLang에서 리스트를 다루는 가장 강력한 방법입니다. x :: _는 “하나 이상의 원소가 있고 첫 번째는 x“를 의미합니다. a :: b :: _는 “두 개 이상의 원소가 있고 처음 두 개는 a와 b“를 의미합니다. 와일드카드 _는 “관심 없는 나머지 부분“을 나타냅니다.

직접 재귀 함수를 작성할 때 match xs with | [] -> ... | x :: rest -> ... 패턴이 거의 항상 등장하는 이유가 여기 있습니다. 리스트의 구조 자체를 코드로 표현하는 가장 자연스러운 방법이기 때문입니다. 패턴 매칭의 전체 기능은 4장에서 자세히 다룹니다.