재귀적 정의와 패턴 매칭을 활용하는 OCaml의 리스트 구조

최근 저희(OCaml 사용에 열정적이고 재미를 느끼는 커뮤니티)는 비어있지 않은 리스트를 설명하기 위한 작은 라이브러리인 nel 패키지를 공개했습니다. (매우 소박한 API를 가지고 있습니다.) 이 데이터 구조의 목적은 applicative validation의 맥락에서 저희 Pidgin 라이브러리의 에러 버퍼 역할을 하는 것입니다. 비어있지 않은 리스트의 semigroup 특성 덕분에, 오류가 발생하더라도 최소한 하나의 오류(error)를 가질 수 있도록 보장합니다. 구현 자체는 매우 간단하고 순진하지만:

type 'a t =
|
( :: ) of 'a * 'a list

그럼에도 불구하고, 이 데이터 구조는 때때로 우리는 리스트처럼 보이는 무언가를 사용하고 싶지만, 더 많은 불변성(invariants)을 유지해야 할 때 (이 경우, 최소한 하나의 요소가 존재함)라는 것을 보여줍니다. 아마도 이것이 저희가 Antonin Décimo(OCaml의 메인테이너 중 한 명으로, OCaml 런타임에 대한 광범위한 기여로 특히 알려져 있음)가 이슈를 제기하며 논의를 시작하게 된 계기가 되었을 것입니다.

nel의 목표는 작고 단일 목적 라이브러리로 남아 있는 것이므로, 이 논의는 아마도 가장 적절한 장소에 속하지 않았을 것입니다 (그래서 해당 이슈는 닫히고 Discuss 스레드로 전환되었습니다). 그럼에도 불구하고, 이는 일부 개발자들이 리스트와 같은 일반적인 구조체에 대해 더 많은 불변성을 가지고 싶어 한다는 것을 보여줍니다. 본 기사에서는 제가 최대한 간단하게 Antonin의 제안을 설명하고, 여러 구현 방식을 제시할 것입니다.

rev를 할 것인가, 아니면 안 할 것인가

리스트는 OCaml에서 매우 편리하게 사용됩니다. 재귀적 정의 덕분에 재귀(recursion)와 패턴 매칭(pattern matching)에 잘 작동하며([]와 ::는 표준 OCaml 생성자로, 약간 다른 리스트의 동물학을 정의하는 데 사용될 수 있으며, 이는 명확화(disambiguation)를 통해 놀랍게도 *비접두사 가능(non-prefixable)*합니다.)

Antonin이 지적하듯이, OCaml 프로그래머들은 folding, mapping, 그리고 리스트 연결에 광범위하게 사용하며, 가능한 한 항상 *꼬리 재귀(tail-recursion)*를 염두에 둡니다 (비록 Tail Recursion Modulo Constructor가 전통적인 접근 방식을 자명하게 만들지만요). 실제로, 복잡성과 중첩의 이유로, 요소들을 리스트의 끝에 추가하는 것보다 요소를 미리 붙인 다음 탐색 끝에서 역순으로 뒤집는 것이 선호됩니다. 예를 들어, map의 순진한 구현은 다음과 같습니다:

let map f list =
let rec aux acc = function
| [] -> List.rev acc
...

보통 **리스트가 역순으로 구축되고 있다는 암묵적인 불변성(implicit invariant)**은 국소적이며 상당히 이해하기 쉽습니다. 하지만 Antonin이 설명하듯이, 사람들은 헝가리안 접두사 스타일의 함수들(자신의 말로 rev_* 등을 사용하는)을 추가하고 싶은 유혹에 빠지기 쉬운데, 이는 rev_append, rev_map, rev_iter 등의 함수 존재를 통해 입증됩니다. 그에 따르면, 이것이 바로 잠재적인 리스트의 타입에서 구축 순서를 추적해야 하는 이유입니다.

흥미롭게도, 제가 이 이슈를 처음 읽었을 때, 저의 초기 직관은 이것이 국소적인 불변성을 포착하기 위해 많은 노력이 필요할 것이라는 것이었습니다. 생각해 보니, 이것은 본질적으로 일반적인 정적 타이핑에 적용될 수 있는 동기 부족 문제였습니다: “테스트를 신중하게 작성하고 쓸 수 있는데 왜 타입에 신경 쓰나요”. 하지만 표현력 수준이 다른 타입 시스템을 다룰 때, 우리는 일반적으로 정적 보장과 사용성 사이의 *균형(trade-off)*을 맞추려고 노력합니다. 언어가 허용하더라도 너무 정확하게 타입을 지정하는 것은 불행하게도 코드를 사용하기 더 복잡하게 만들 수 있습니다.

Xavier Van de Woestyne와 간략히 논의한 후, 우리가 국소적이라고 생각했던 불변성, 즉 리스트를 역순으로 구축하는 것이 사실 그렇게 국소적이지 않다는 것을 빠르게 깨달았습니다. 실제로 rev_append (그리고 확장적으로 rev_map 등)의 존재가 이를 보여줍니다.

) points는 성능상의 이유로 리스트를 역순으로 뒤집을 책임(예: 다른 방식으로 구성된 리스트의 끝에 추가할 때)을 호출자에게 남겨두는 것을 선호한다는 사실을 명확히 보여줍니다. 우리는 심지어 Xavier가 Merlin에 기여한 초기 작업 중 하나인 'destruct: Residual patterns 제거'에서 이러한 제약이 완화되는 매우 구체적인 예를 찾을 수 있었습니다.
리스트를 역순으로 뒤집어야 하는지 여부 추적은 특정 문제 클래스에 유용해 보입니다.

비록 이것이 nel 라이브러리의 범위를 벗어났지만, 이 연습은 충분히 재미있어서 시도할 가치가 있었고 (잠재적으로 유용한 라이브러리로 이어질 수 있습니다). Antonin이 제가 절대 아닌 타입 마법사를 요구하지만, 다음 섹션에서 제가 생각해낸 몇 가지 아이디어를 제시하겠습니다.

첫 번째 구성 기반(by-construction) 접근 방식

OCaml에서 흔히 그렇듯이, 구성 단계에서 속성을 강제하고 싶을 때 우리는 GADTs에 의존합니다. GADT는 생성자(constructors)를 통해 타입 매개변수에 제약 조건을 인코딩할 수 있게 해주며 (지역 타입 동등성 사용). 먼저, 저는 역순 및 비역순 리스트를 인덱싱할 수 있도록 하는 몇 가지 *태그(tags)*를 정의합니다:

type rev = private R
type ord = private O

저는 이들에게 생성자를 부여하여 모듈 외부에서 컴파일러가 rev와 ord를 구별한다고 간주하도록 합니다 (만약 그것들이 추상적이라면), 이는

이 방식을 사용하면 역순 리스트만 구성할 수 있습니다. 예를 들어 (제 타입에 예쁜 프린터를 설치하지 않아서 읽기가 조금 번거롭습니다):

# [1] ;; 
- : (rev, int) glist = (::) (1, [])

보시다시피 [1]은

(실제로는 1 :: []입니다)
이 태그가 rev인 리스트를 올바르게 반환합니다. 이제 우리는 역순이 아닌 리스트도 기술할 수 있기를 바랍니다 (그렇지 않으면 이 모듈은 별로 유용하지 않을 것입니다). 제 아이디어는 역순 리스트를 역전시키는 목적을 가진 생성자를 추가하는 것일 뿐입니다:

type (_, _) glist = 
| [] : (rev, 'a) glist
| ( :: ) : 'a * (rev, 'a) glist -> (rev, 'a) glist
...

type (_, _) glist = 
| [] : (rev, 'a) glist
| ( :: ) : 'a * (rev, 'a) t -> (rev, 'a) glist
...

이제 유용한 조합자(combinators)들을 만들 수 있으며 타입 추론이 태그가 올바르게 할당되도록 안내할 것입니다:

# let rev_empty = [] ;; 
val rev_empty : (rev, 'a) glist = []
# let empty = Ord [] ;; 
...

이 정의의 직관에 반하는 부분은 우리가 실제로 리스트를 역전시키지(reorder) 않는다는 것입니다. 이를 위해 먼저 두 개의 함수를 생성할 것입니다:

val of_rev_list : 'a list -> (rev, 'a) glist
val of_list : 'a list -> (ord, 'a) glist

이 두 함수의 타입에 담긴 직관만으로 충분해야 합니다. 첫 번째는 이미 역순인 리스트로부터 역순 리스트를 단순히 구성하는 반면, 두 번째는 역순이 아닌 리스트로부터 리스트를 구성합니다. of_rev_list 구현부터 시작하겠습니다:

:

let of_rev_list list = 
let rec aux : (rev, 'a) glist -> 'a list -> (rev, 'a) glist = 
fun acc -> function
...

우리는 리스트의 모든 요소를 순회하며 점진적으로 glist를 재구성할 것입니다. 이상하게 보일 수 있는 점은 리스트가 역순으로 구축되고 있다는 것입니다:

# of_rev_list [1; 2; 3] ;; 
- : (rev, int) glist = (::) (3, (::) (2, (::) (1, [])))

하지만 실제 역전(정규 리스트로의 투영)은 나중에 이루어질 것입니다. 역순이 아닌 리스트를 변환하기 위해 우리는 이미 ord가 있습니다.

, 따라서 함수 구현이 매우 간단합니다:

let of_list list =
list
|> of_rev_list
...

흥미로운 점은 (제 관점에서) 이 인코딩의 핵심입니다. 역순되지 않은 리스트는 역순된 리스트와 정확히 같은 구조를 가지며 (이는 그 다소 이상한 본질을 강화합니다). 실제로 유일한 차이점은 역순되지 않은 리스트가 Ord 생성자에 래핑되어 있어 ord 태그를 유지한다는 것입니다:

# of_list [1; 2; 3] ;; 
- : (ord, int) glist = Ord ((::) (3, (::) (2, (::) (1, []))))

이제 리스트를 처음부터 그리고 기존의 일반 리스트로부터 구성할 수 있게 되었으므로, to_list 조합자를 제공하여 실제로 역순을 수행할 수 있습니다:

(* 두 가지 유형의 리스트([rev] list와 [ord] list)를 처리할 수 있도록 하고 싶습니다 *) 
let to_list : type a. (a, 'b) glist -> 'b list = fun glist ->
...

이제 타입에서 역순 추적을 할 충분한 도구를 갖게 되었습니다. 예를 들어, 최종 결과를 역순하지 않는 일반 리스트에 대한 map 함수를 구현한다고 상상해 봅시다:

# let my_map f list = 
let rec aux acc = function
| List.[] -> acc
...

이것을 빠르게 테스트할 수 있습니다. 예상대로, 우리의 결과는 역순되어야 합니다:

# [1; 2; 3; 4; 5] |> my_map (fun x -> x + 42) |> to_list ;; 
- : int list = [47; 46; 45; 44; 43]

또한 ord 함수를 사용하여 역순 해제가 작동하는지 확인할 수도 있습니다:

# [1; 2; 3; 4; 5] |> my_map (fun x -> x + 42) |> ord |> to_list ;; 
- : int list = [43; 44; 45; 46; 47]

이 타입의 목적이 아마도 인덱스 리스트를 구축하여 일반 리스트로 변환하는 것만은 아닐지라도, 여전히 우리의 glist에 대해 매핑과 같은 일반 함수들을 구축할 수 있으며, 이는 물론 그 태그를 보존합니다 (리스트에 매핑하는 것은 역순을 변경하지 않습니다):

let map : type a. ('b -> 'c) -> (a, 'b) glist -> (a, 'c) glist = 
fun f xs ->
let rec aux : (rev, 'c) glist -> (rev, 'b) glist -> (rev, 'c) glist =
...

문제가 해결된 것처럼 보이지만, 주의 깊게 읽는 독자들은 이 제안에 몇 가지 주요 약점을 발견했을 것입니다 (그래서 저는 원래 논의에서 이것을 공유하지 않았습니다). 실제로 이 해결책은 상당히 비용이 많이 듭니다:

• 일반 리스트를 구성하려면 전체 리스트를 순회해야 합니다 (이는 일반적으로 빈 리스트에서 시작하여 요소를 점진적으로 누적하는 방식으로 작동하는 재귀 알고리즘의 경우, 무시할 수 있을 수도 있습니다).

• 더 성가신 문제는 다음과 같습니다. 일반 리스트를 생성하기 위해서는 어쨌든 전체 리스트를 순회해야 합니다. 이는 ord 태그가 지정된 리스트를 일반 리스트로 변환하려면 리스트를 한 번 순회하는 반면, rev 태그가 지정된 리스트를 일반 리스트로 변환하려면 한 번 순회한 다음 역순으로 만들고 또 다른 순회가 필요하다는 것을 의미합니다.

제가 추가하고 싶은 마찰 지점은 다음과 같습니다. 이 해결책은 리스트 API를 다시 작성해야 하며, 타입 레벨 추적 측면에서 약속을 (어색하게) 이행하는 것처럼 보이지만, 합리적인 범위의 프로젝트에는 실행 가능한 해결책처럼 보이지 않습니다. 그럼에도 불구하고, 이는 재미있는 접근 방식이었습니다 (데이터 구조의 생성자를 통해 제약 조건을 부여하는 방식) 그리고 성능에 덜 민감한 경우 흥미롭고 유용할 수 있습니다.

제가 실제로 제시했던 제안을 살펴보겠습니다. 기계 장치가 적고, 아마도 덜 흥분되겠지만, 저의 관점에서는 더 많은 가능성을 지닌 접근 방식입니다.

두 번째 제약 기반 접근 방식

GADTs를 사용하여 새로운 타입을 정의하는 이 우회 경로는 그럼에도 불구하고 리스트의 생성자와 그 API가 역순을 유지하기 위해 제약 조건을 강제할 수 있다는 직관을 우리에게 주었습니다. 이 첫 번째 접근 방식에서 영감을 받아, 우리는 펌탄 증인(phantom witness)을 사용하여 리스트 타입을 다시 작성할 필요 없이 유사한 일련의 보장을 유지하는 제약 기반 접근 방식을 쉽게 사용할 수 있습니다.

이번에는 생성자 레벨에서 제약 조건을 덜 부과할 수 있게 되었기 때문에(GADTs 사용 덕분에), 인터페이스를 설명하는 것부터 시작하겠습니다. 이전과 마찬가지로, 태그를 설명하는 것부터 시작합니다:

type rev = [ `Rev ]
type ord = [ `Ord ]

이번에는 우리가 곧 살펴볼 이유 때문에 다형적(polymorphic) 변이형(variants)을 사용합니다. 이제 우리는 *역순(reversal)*을 유지하는 리스트 타입을 설명할 수 있습니다:

type ('ord, 'a) olist = 
private 'a list
constraint 'ord = [< `Rev | `Ord ]

우리는 olist를 수동으로 구성할 수 없도록 하는 리스트의 *비공개 별칭(private alias)*을 설명합니다. 그런 다음 'ord 타입 매개변수에 제약 조건을 추가하여, 이것이 반드시 [< Rev | Ord ] 인스턴스여야 함을 보장합니다. 이것이 우리의 태그 역할을 할 것입니다. 이것이 바로 우리가 태그를 다형적 변이형을 사용하여 설명하는 이유입니다: 이를 통해 rev와 ord의 합집합(여기서는 폐쇄된 합집합)인 타입을 설명할 수 있게 됩니다.

include Olist