순수 함수형 데이터 구조 - ChoDragon9/posts GitHub Wiki
대부분의 함수형 언어는 연산 순서에 따라 미리 계산하는(strict evaluation) 언어나 지연 계산(Lazy evaluation) 언어로 분류 할 수 있다.
두 연산 순서의 차이는 함수 인자를 처리할 때 분명히 드러난다. 미리 계산하는 언어에서는 함수의 인자를 미리 계산한 다음 함수 본문을 계산한다. 지연 계산 언어에서는 필요할 때(on-demand) 인자를 계산한다. 즉, 함수를 호출할 때 인자를 계산하지 않는 형태로 전달하고 함수의 결과를 계산하기 위해 그 인자가 필요할 때만 계산한다. 나아가 어떤 인자를 한번 계산하고 나면 그 결과를 캐시에 넣고, 해당 값이 다시 필요할 때는 값을 재계산하는 대신 캐시해둔 값을 사용한다. 이런 캐싱을 메모화라고 한다.
함수형 데이터 구조의 독특한 특성 하나는 함수형 데이터 구조가 늘 영속적(persistent)이라는 점이다. 함수형 데이터 구조는 갱신해도 예전 버전을 파괴하지 않는다. 대신 새로운 버전의 데이터 구조가 생겨서 이전 버전과 공존한다.
영속성은 기존 데이터 구조에서 변경에 따라 바뀌어야 하는 부분들을 복사한 후, 원본 대신 복사본을 변경함으로써 이뤄진다. 노드를 직접 변경하는 일이 없으므로 갱신이 이뤄져도 기존 노드들은 영향을 받지 않고, 어느 한쪽을 바꿔도 다른 쪽에 바꾼 내용이 전파될지 걱정할 필요 없이 새 버전과 옛 버전을 공유할 수 있다.
함수형 프로그래밍에서는 연결 리스트가 좀 더 널리 쓰인다. 모든 리스트가 지원해야 하는 핵심 함수는 스택 추상화에서 볼 수 있다.
SML에서 signature는 모듈의 시그니처(모듈이 제공하는 이름과 타입 정보)를 정의하는 데 쓰인다. signature로 선언된 것을 structure로 구현하고, open으로 불러오거나, 구현.함수() 처럼 전체 이름으로 해당 모듈이 제공하는 기능을 사용할 수 있다.
SML에서 'a는 그리스 문자를 뜻한다. 함수형 언어에 대한 문헌에서 보통 다형성이 있는 타입의 타입 파라미터를 표현할 때 그리스 문자를 사용하는 데, 아스키 키보드에서 그리스 문자를 입력할 수 없으므로 'a를 사용한다.
signature STACK =
sig
type 'a Stack
val empty: 'a Stack
val isEmpty: 'a Stack -> bool
val cons: 'a * 'a Stack -> 'a Stack
val head: 'a Stack -> 'a
val tail: 'a Stack -> 'a Stack
end- SML의 함수는 항상 인자와 리턴값이 존재한다.
- 상태를 격리해서 보관하는 기능이 없다.
type STACK<T> = {
readonly empty: T[]
isEmpty(stack: T[]): boolean
cons(item: T, stack: T[]): T[]
head(stack: T[]): T
tail(stack: T[]): T[]
}스택 추상화를 SML 내장 리스트 타입으로 구현
structure List: STACK =
struct
type 'a Stack = 'a list
val empty = []
fun isEmpty s = null s
fun cons (x, s) = x :: s
fun head s = hd s
fun tail s = tl s
end- 모듈화를 통해 응집성을 높힌다.
const List: STACK<any> = {
empty: [],
isEmpty(stack: any[]): boolean {
return !!stack.length
},
cons(item: any, stack: any[]): any[] {
return [item, ...stack]
},
head([head]: any[]): any {
return head
},
tail([, ...tail]: any[]): any[] {
return tail
}
}
const emptyList = List.empty // []
const oneList = List.cons(1, emptyList) // [ 1 ]
const twoList = List.cons(2, oneList) // [ 2, 1 ]
const head = List.head(twoList) // 2
const tail = List.tail(twoList) // [ 1 ]스택 추상화를 직접 정의한 데이터 타입을 사용해 구현
structure CustomStack: STACK =
struct
datatype 'a Stack = NIL | CONS of 'a * 'a Stack
val empty = NIL
fun isEmpty NIL = true | isEmpty _ = false
fun cons (x, s) = CONS(x, s)
fun head NIL = raise Empty
| head (CONS (x, s)) = x
fun tail NIL = raise Empty
| tail (CONS (x, s)) = s
end
val emptyList = List.empty
val oneList = List.cons(1, emptyList)
val remains = List.tail(oneList)두 리스트를 서로 연결하는 것으로 명령형과 함수형을 비교한다.
명령형 방식에서는 리스트의 첫 셀과 마지막 셀에 대한 포인터를 유지함으로써 O(1)만에 두 리스트를 이어 붙일 수 있다. 첫 번째 리스트의 마지막 셀이 두 번째 리스트의 첫 번째 셀을 가리키도록 변경함으로써 쉽게 구현할 수 있다. 단 두 리스트를 모두 파괴한다는 점에 유의해야 한다. 두 리스트를 이어 붙인 뒤 두 리스트를 재사용할 수 없다.
함수형 방식에서는 첫 번째 리스트의 마지막 셀을 이런 식으로 변경할 수 없다. 대신 우리가 마지막 셀을 복사하면서, 복사본에서 다음 셀을 가리키는 포인터가 두 번째 리스트의 첫 셀을 가리키게 만든다. 그런 다음, 끝에서 두 번째 셀을 복사하면서 꼬리 포인터가 방금 생긴 마지막 셀의 복사본을 가리키게 한다. 이런 과정을 첫 번째 리스트를 모두 다 복사할 때까지 반복한다. 이 경우 영속성이 생겨나는 대신 복사에 O(n)이라는 추가 비용이 든다.
infix 3 ++
fun [] ++ ys = ys
| (x :: xs) ++ ys = x :: (xs ++ ys)
val xs = [0, 1, 2]
val ys = [3, 4, 5]
val zs = xs ++ ys; (* [0,1,2,3,4,5] *)// fun [] ++ ys = ys
// | (x :: xs) ++ ys = x :: (xs ++ ys)
const cons = ([x, xs], ys) => {
return x === undefined ?
ys :
[x, cons(xs, ys)]
}
// val xs = [0, 1, 2]
// val ys = [3, 4, 5]
// val zs = xs ++ ys;
const xs = [0, [1, [2, []]]]
const ys = [3, [4, [5, []]]]
const zs = cons(xs, ys) //[0,[1,[2,[3,[4,[5,[]]]]]]]복사와 공유라는 개념을 보여주는 또 다른 예로 update를 들 수 있다. update함수는 리스트에서 주어진 인덱스(index)에 해당하는 원소의 값을 바꾼다. 여기서도 인자로 주어진 리스트 전체를 복사할 필요는 없다. 대신 변경해야 할 노드와 그 노드를 직간접적으로 가리키는 노드들을 복사한다.
다시 말해, 한 노드를 변경하려면 리스트의 시작부터 변경할 대상 노드에 이르는 경로에 있는 모든 노드를 변경한다. 이 경로에 있지 않는 다른 노드들은 모두 원본과 변경본에서 공유된다. 예를 들어 노드가 5개인 리스트에서 3번째 노드를 변경한 경우를 보여준다. 앞으로부터 3개의 노드를 복사하고 나머지 2개는 공유한다.
fun update (x :: xs, 0, y) = y :: xs
| update (x :: xs, i, y) = x :: update (xs, i - 1, y)
val xs = [0, 1, 2, 3, 4]
val ys = update(xs, 2, 7)// fun update (x :: xs, 0, y) = y :: xs
// | update (x :: xs, i, y) = x :: update (xs, i - 1, y)
const update = ([x, ...xs], i, y) => {
return i === 0 ?
[y, ...xs] :
[x, ...update(xs, i - 1, y)]
}
// val xs = [0, 1, 2, 3, 4]
// val ys = update(xs, 2, 7)
const xs = [0, 1, 2, 3, 4]
const ys = update(xs, 2, 7) // [0, 1, 7, 3, 4]타입 생성자(TypeConstructor) : http://mlton.org/TypeConstructor
이진 검색 트리는 원소들이 대칭적 순서(Symmetric Order)를 따라 저장된 이진 트리를 말한다. 대칭적 순서란 어떤 노드에 저장된 값이 그 노드의 왼쪽 하위 트리에 들어 있는 모든 값보다 크고 그 노드의 오른쪽 하위 트리에 들어 있는 모든 값보다 작다는 뜻이다. 이를 다음 SML 타입으로 표현할 수 있다.
datatype Tree = E | T of Tree * Elem * Tree
TypeScript에서는 제귀적인 타입을 선언할 수 없기 때문에 객체로 만들어야 함.
type EmptyNode = null
type TreeNode<T> = EmptyNode | {
left: TreeNode<T>
value: T
right: TreeNode<T>
}여기서 원소 Elem의 타입인 T는 모든 원소의 순서가 정해지는(totally-ordered) 타입이어야 한다.
집합을 구현하기 위해 이 트리 표현을 사용할 것이다. 집합의 최소 시그니처를 보여준다.
signature SET =
sig
type Elem
type Set
val empty: Set
val insert: Elem * Set -> Set
val member: Elem * Set -> bool
endtype TreeType<T> = {
empty: TreeNode<T>
insert(elem: T, tree: TreeNode<T>): TreeNode<T>
member(elem: T, tree: TreeNode<T>): boolean
}member 함수는 주어진 원소를 트리 루트와 비교하면서 트리 검색을 시작한다.
- 질의한 값이 트리 루트보다 작다면 재귀적으로 왼쪽 하위 트리를 검색한다.
- 반대로 질의한 값이 트리 루트보다 크면 오른쪽 하위 트리를 재귀적으로 검색한다.
- 질의한 값과 트리 루트가 같다면 true를 반환한다.
- 빈 트리가 도착했다면 질의한 값과 같은 원소가 트리에 없으므로 false를 반환한다.
fun member (x, E) = false
| member (x, T(a, y, b)) =
if x < y then member(x, a)
else if x > y then member(x, b)
else trueinsert 함수는 member와 마찬가지 전략을 사용해 트리를 검색한다. 다만, 검색을 진행하는 동안 방문하는 노드를 복사한다는 점이 member와 다르다. 빈 노드에 도착하면 insert는 그 빈 노드를 새로운 원소가 들어 있는 노드로 바꾼다.
fun insert (x, E) = T (E, x, E)
| insert (x, s as T (a, y, b)) =
if x < y then T (insert(x, a), y, b)
else if x > y then T (a, y, insert(x, b))
else sconst Tree: TreeType<number> = {
empty: null,
member(elem: number, tree: TreeNode<number>): boolean {
if (tree === Tree.empty) {
return false
}
const {left, value, right} = tree
if (elem < value) {
return Tree.member(elem, left)
} else if (elem > value) {
return Tree.member(elem, right)
} else {
return true
}
},
insert(elem: number, tree: TreeNode<number>): TreeNode<number> {
if (tree == Tree.empty) {
return {
left: Tree.empty,
value: elem,
right: Tree.empty
}
}
const {left, value, right} = tree
if (elem < value) {
return {
left: Tree.insert(elem, left),
value,
right
}
} else if (elem > value) {
return {
left,
value,
right: Tree.insert(elem, right)
}
} else {
return tree
}
}
}const one = Tree.insert(3, Tree.empty)
console.log(one)
const two = Tree.insert(2, one)
console.log(two)
const three = Tree.insert(4, two)
console.log(three)
const four = Tree.insert(1, three)
console.log(four)
const five = Tree.insert(5, four)
console.log(five)
console.log(Tree.member(4, five))도서에 없는 부분임
- 트리가 비어 있거나 삭제할 elem가 멤버가 아니면 tree 반환
- 삭제할 elem를 찾을 때 마다 새로 생성함
- 삭제할 elem를 Empty로 변경
type TreeType<T> = {
...
remove(elem: T, tree: TreeNode<T>): TreeNode<T>
}
const Tree: TreeType<number> = {
...
remove(elem: number, tree: TreeNode<number>): TreeNode<number> {
if (tree === Tree.empty || !Tree.member(elem, tree)) {
return tree
}
const {left, value, right} = tree
if (elem < value) {
return {
left: Tree.remove(elem, left),
value,
right
}
} else if (elem > value) {
return {
left,
value,
right: Tree.remove(elem, right)
}
} else {
return Tree.empty
}
}
}SML 펑터를 사용해 이진 검색 트리를 구현한 것을 보여준다. 이 펑터는 원소 타입과 그 타입이 지원해야 하는 비교 연산을 파라미터로 받는다. 비교 연산을 지원하는 타입을 파라미터로 사용할 일이 많이 때문에, 이를 ORDERED라는 별도의 시그니처로 만들어서 스트럭처가 그 시그니처를 따르도록 만들었다.
SML에서 다른 타입을 인자로 받아서 스트럭처를 반환하는 모듈이 펑터다. 이름은 같지만 함수형 프로그래밍에서 일반적으로 말하는 펑터(매핑 함수인 map을 지원하는 타입 클래스)와는 구분해야 한다.
signature ORDERED =
sig
type T
val eq: T * T -> bool
val lt: T * T -> bool
val leq: T * T -> bool
end
functor UnbalancedSet (Element: ORDERED): SET =
struct
type Elem = Element.T
datatype Tree = E | T of Tree * Elem * Tree
type Set = Tree
val empty = E
fun member (x, E) = false
| member (x, T(a, y, b)) =
if Element.lt(x, y) then member(x, a)
else if Element.lt(y, x) then member(x, b)
else true
fun insert (x, E) = T (E, x, E)
| insert (x, s as T (a, y, b)) =
if Element.lt(x, y) then T (insert(x, a), y, b)
else if Element.lt(y, x) then T (a, y, insert(x, b))
else s
end마이어스(Myers)는 영속적인 이진 검색 트리를 구현하기 위해 복사와 공유를 사용했다. 사나크(Sarnak)와 타잔(Tarjan)은 모든 노드를 복사하는 방식으로 영석적인 데이터 구조를 구현하는 일반적인 기법에 경로 복사(path copying)라는 용어를 처음 붙였다. 영속적인 데이터 구조를 만드는 다른 일반적인 기법으로는 드리스콜(Driscoll), 사나크, 슬리터(Sleator), 타잔의 기법과 디에츠(Dietz)의 기법이 있다. 하지만 이 기법들은 완전히 함수적인 기법은 아니다.
여기서는 지연 계산 기본 도구로 $ 표기법을 소개한다. $ 표기법으로 작성된 프로그램을 다른 지연 계산 표기로 변환하기는 쉽다.
$ 표기법에서는 일시중단된 계산을 표기하기 위해 'a susp라는 타입을 소개한다. 이 타입에는 $라는 단항 생성자[1]만 존재한다. 'a susp와 $를 마치 일반적인 데이터 타입 선언으로 정의한 것과 똑같이 작동하는 것으로 우선 어림짐작할 수 있다.
[1] 단항 생성자: 타입 생성자에서 인자를 단항만 넣을 수 있다는 의미이다.
datatype 'a susp = $ of 'a- T 타입의 식 e를 사용해 $e라고 쓰면 새로운 T 타입의 일시중단인 T susp를 만들 수 있다.
- 이미 존재하는 일시중단에서 내용을 끄집어낼 때는 $p라는 패턴을 사용한다.
- 이때 p라는 패턴이 T라는 타입의 값과 매치된다면 $p는 T susp 타입의 일시중단과 매치된다.
요약하면 즉시 계산하지 않고 패턴 매치가 일어나면 인자 식을 계산하고 다른 패턴에 대해 매치시키면 메모했던 값을 사용한다.
$의 영역(scope)은 최대한 오른쪽으로 확장된다. 예를 들어 $f x는 (
스트림(지연 계산 리스트(lazy list)라고도 함)은 일반 리스트와 비슷하다. 스트림과 일반 리스트의 차이는 스트림의 각 셀이 체계적으로 일시중단된 식으로 이뤄진다는 점이다. 스트림의 타입은 다음과 같다.
datatype 'a StreamCell = Nil | Cons of 'a * 'a Stream
withtype 'a Stream = 's StreamCell susp1, 2, 3을 원소로 포함하는 간단한 스트림은 다음과 같이 쓸 수 있다.
$Cons (1, $Cons (2, $Cons (3, $Nil)))'a list susp이 표현하는 계산은 근본적으로 모놀리식(monolithic)하다. 즉, 일시중단된 'a list susp 타입의 값을 강제 계산하면 리스트 원소가 모두 생길 때까지 계산이 이뤄진다. 반면 스트림이 표현하는 계산은 점진적(incremental)이다. 가장 바깥쪽셀을 만들 때까지만 실행이 이뤄지고, 나머지 부분은 일시중단된다. 이런 동작 방식은 스트림처럼 내부에 일시중단을 내포하는 데이터 타입에서 흔히 있는 방식이다.
이 함수가 만드는 일시중단은 두 인자를 각각 강제 계산해서 만들어지는 두 리스트를 연결해 결과를 만든다. 따라서 이 일시중단은 모놀리식이다. 그래서 이 함수(++)를 모놀리식하다고 말하기도 한다.
fun s ++ t = $(force s @ force t)
(* 또는 *)
fun lazy ($xs) ++ ($ys) = $(xs @ ys)스트림의 경우 이어붙이기 함수는 다음과 같다.
fun lazy ($Nil) ++ t = t
| ($Cons (x, s)) ++ t = $Cons (x, s ++ t)이 함수는 즉시 일시중단을 반환한다. 그 일시중단을 강제로 계산하면 $ 패턴과 매치시키기 위해 왼쪽 스트림의 첫번째 셀을 요청한다. 재귀 호출은 단지 다른 일시중단을 만들어내기만 하고, 다른 계산을 수행하지 않는다. 따라서 이 함수가 표현하는 계산은 점진적이다.
워즈워스(Wadsworth)는 람다 계산법의 정규 순서 축약(NOR, normal-order reduction)에 대한 최적화로 지연 계산을 처음 제안했다. 뷜레민(Vuillemin)은 나중에 일부 제약이 가해진 환경에서는 지연 계산이 최적의 계산 전략임을 증명했다. 지연 계산의 엄밀한 수학적 의미에 대한 연구가 이미 광범위하게 존재한다.
란딘(Landin)은 스트림을 소개했다. 하지만 란딘의 스트림에는 메모화가 없었다. 프리드먼(Friedman)과 와이즈(Wise), 핸더슨(Handerson)과 모리스(Morris)는 란딘의 스트림에 메모화를 추가해 확장했다.
미치(Michie)는 함수 인자와 결괏값을 캐시하도록 함수에 부가적인 장치를 추가하는 과정에 메모화(memoization)라는 단어를 처음 사용했다. 일시중단을 영항 함수(인자가 없는 함수(nullary function))로 간주하면, 메모화의 의해 덧붙여진 필드들이 일시중단 시 사라져버린다. 휴스(Hughes)는 미치가 원래 생각했던 그 의미 그대로 함수형 프로그래밍에 메모화를 적용했다.
지연 계산의 두 가지 구성요소(계산을 지연시키는 것과 결과를 메모하는 것)는 알고리즘 설계에 오래전부터 쓰여왔던 기법이다. 물론 이 두 기법이 항상 함께 쓰였던 것은 아니다. 비용이 비쌀 가능성이 있는 계산(보통 데이터를 제거하는 연산이 비싼 경우가 많다)을 지연시키는 아이디어는 해시 테이블, 우선 순위 큐, 검색 트리 등에서 좋은 결과를 보였다. 한편 메모화는 동적 프로그래밍이나 경로 압축의 기본적인 원리라 할 수 있다.