재귀적 데이터 구조

Recursive data structures(재귀적인 데이터 구조)

대수적 데이터 타입내 생성자는 여러개의 필드를 가질수 있고(또는 필드가 없고), 각 필드는 어떤 구체적인 타입이어야 합니다. 이점을 염두에 두고 우리는 생성자가 동일한 타입의 필드들을 가진 타입들 만들 수 있습니다. 이것을 사용하면 재귀적인 데이터 타입을 만들 수 있습니다. 어떤 타입의 값 하나에 타입의 값들을 포함할 수 있는 재귀적인 데이터 타입에는 동일한 타입의 값들이 더 많이 포함됩니다.

[5]은 5:[]와 같습니다. :의 왼쪽은 값이고 오른쪽은 빈 리스트입니다. 마찬가지로 [4,5]는 4:(5:[])이고, 첫번째 :의 왼쪽에는 구성값이 오른쪽에는 리스트가 있습니다. 3:(4:(5:6:[]))는 3:4:5:6:[]나 [3,4,5,6]과 같습니다.

따라서 리스트는 빈리스트이거나 구성값 + : + 다른 리스트(or 빈리스트)의 조합이라고 볼 수 있습니다.

이제 우리만의 리스트를 구현하기 위해 대수적 데이터 타입을 사용해보겠습니다.

data List a = Empty | Cons a (List a) deriving (Slow, Read, Eq, Ord)

좀 전에 리스트에 대해서 정의한것과 비슷하게 List는 빈리스트이거나 head와 리스트의 조합입니다. 이것을 레코드를 사용해서 구현하면 좀 더 이해하기 쉽습니다.

data List a = Empty | Cons { listHead :: a, listTail :: List a} deriving (Show, Read, Eq, Ord)

여기서 Cons는 :입니다. :는 실제로 값과 다른 리스트를 받아서 리스트를 리턴하는 생성자 입니다. 이 생성자는 두개의 필드를 가지고있고, 하나는 a 타입이고 다른 필드는 [a] 타입입니다.

ghci> Empty
Empty
ghci> 5 `Cons` Empty
Cons 5 Empty
ghci> 4 `Cons` (5 `Cons` Empty)
Cons 4 (Cons 5 Empty)
ghci> 3 `Cons` (4 `Cons` (5 `Cons` Empty))
Cons 3 (Cons 4 (Cons 5 Empty))

infix 방식의 Cons 생성자는 :를 사용하는 것과 유사합니다. Empty는 []와 유사하고, 4 `Cons` (5 `Cons` Empty)는 4:(5:[])와 유사합니다.

특수 문자로만 구성하여 자동으로 infix가 되는 함수를 정의할 수 있습니다. 또한 데이터 타입을 리턴하는 함수이기 때문에 생성자에서도 동일한 일을 할 수 있습니다.

infixr 5 :-:
data List a = Empty | a :-: (List a) deriving (Show, Read, Eq, Ord)

우선 새로운 문법인 fixity 선언에 대해서 알아보겠습니다. 함수를 연산자로 정의할 때, 함수를 사용하여 fixity를 제공할 수 있습니다. fixity는 연산자 우선순위와 왼쪽 또는 오른쪽 방향을 나타냅니다. 예를들어, *의 fixity는 infixl 7 *이고, +의 fixity는 infixl 6 입니다. 이것의 둘다 왼쪽 연관(즉, 4 * 3 * 2는 (4 * 3) * 2)이고 *가 +보다 fixity가 크기때문에 우선순위가 높은것을 의미합니다. 그래서 5 * 4 + 3은 (5 * 4) + 3입니다.

이제 리스트 타입에 리스트를 작성할때 Cons a (List a) 대신 a :-: (List a)를 사용할 수 있습니다.

ghci> 3 :-: 4 :-: 5 :-: Empty
(:-:) 3 ((:-:) 4 ((:-:) 5 Empty))
ghci> let a = 3 :-: 4 :-: 5 :-: Empty
ghci> 100 :-: a
(:-:) 100 ((:-:) 3 ((:-:) 4 ((:-:) 5 Empty)))

타입이 Show 타입클래스에 속할때, 하스켈은 생성자가 prefix 함수인 것처럼 보여서 연산자를 괄호로 둘러싸서 표시합니다. (4 + 3은 (+) 4 3과 동일)

리스트를 두개를 합치는 함수를 만들어 보겠습니다. 아래 예제는 일반적인 리스트에서 ++를 정의하는 방법입니다.

infixr 5 ++
(++) :: [a] -> [a] -> [a]
[]     ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)

새로 정의한 리스트로 .++ 연산자로 정의하면 아래와 같습니다.

infixr 5 .++
(.++) :: List a -> List a -> List a
Empty .++ ys = ys
(x :-: xs) .++ ys = x :-: (xs .++ ys)

이렇게 정의된 함수는 아래와 같이 동작될 것 입니다.

ghci> let a = 3 :-: 4 :-: 5 :-: Empty
ghci> let b = 6 :-: 7 :-: Empty
ghci> a .++ b
(:-:) 3 ((:-:) 4 ((:-:) 5 ((:-:) 6 ((:-:) 7 Empty))))

이제 어떻게 (x :-: xs) 패턴에 매칭되는지 살펴보겠습니다. :-:는 새로 정의한 리스트 타입에 생성자이기 때문에 매칭될 수 있습니다. 기본 리스트 타입에 정의된 :와 []에 대해서도 동일합니다. 패턴매칭은 (유일하게) 생성자에 매칭되어 동작하기 때문에 8이나 a같은 것도 기본적으로 각각 숫자, 문자 타입의 생성자에 매칭되어 동작합니다.

이제부터 이진 검색 트리를 구현해 볼 것 입니다. 여기서 이진 검색 트리는

  • 한 노드는 두 노드를 가리키고, 하나는 왼쪽에 다른 노드는 오른쪽에 있습니다.
  • 오른쪽에 있는 노드는 왼쪽에 있는 노드보다 큰 값을 가지고 있습니다.
  • 각 노드는 아무것도 가리키지 않거나 한개, 두개의 노드를 가리킬 수 있습니다.
  • 각 로드에는 최대 두개의 하위 트리가 있습니다.
  • 어떤 노드의 왼쪽 하위 트리의 모든 노드는 어떤 노드보다 항상 작습니다. 반대로 오른쪽 하위 트리는 항상 큽니다.

Data.Set의 Set과 Data.Map의 Map은 균형잡힌 이진 검색 트리를 사용하여 구현되었습니다. 균형잡힌 트리는 한쪽으로 치우치지않고 항상 좌우가 균형잡힌 트리를 의미합니다. 여기서는 균형잡힌 트리가 아닌 일반적인 이진 검색 트리를 구현할 것 입니다.

먼저 트리는 비어있거나 어떤 값과 두개의 트리를 가진 한개의 노드입니다. 이것은 대수적 데이터 타입으로 정의하면 아래와 같습니다.

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show, Read, Eq)

수동으로 트리를 만드는것 대신에 여기서는 트리와 노드를 받아서 트리를 만들고 노드를 삽입하는 함수를 만들 것입니다. 루트 노드에 새로운 노드를 넣으려면, 값을 비교해서 값이 작으면 왼쪽에 크면 오른쪽에 넣어야 합니다. 트리의 모든 노드를 거쳐서 빈트리를 만날때까지 동일한 작업을 반복합니다. 빈트리를 만나면, 빈트리 대신 값을 포함한 노드를 넣습니다.

C와 같은 언어에서는 트리안에 포인터와 값들을 수정하여 이런 작업을 합니다. 하스켈에서는 트리를 수정하지 않습니다. 따라서 왼쪽이나 오른쪽으로 갈때마다 새로운 하위트리를 만들어야하고, 삽입 함수는 완전히 새로운 트리를 리턴합니다. 왜냐하면 하스켈은 실제로 포인터 개념이 없고 그냥 값이기 때문입니다. 그러므로 삽입 함수의 타입은 a -> Tree a -> Tree a와 같이 될 것 입니다. 이 함수는 노드와 트리를 받아서 입력받은 노드를 포함한 새로운 트리를 리턴합니다. 이것은 비효율적인 것 처럼 보이지만 laziness가 이 문제를 해결합니다.

아래 싱글톤 트리(한개의 노드만 가진 트리)를 만드는 유틸리티 함수와 트리에 노드를 삽입하는 함수를 구현하였습니다.

singleton :: a -> Tree a
singleton x = Node x EmptyTree EmptyTree

treeInsert :: (Ord a) => a -> Tree a -> Tree a
treeInsert x EmptyTree = singleton x
treeInsert x (Node a left right)
    | x == a = Node x left right
    | x < a  = Node a (treeInsert x left) right
    | x > a  = Node a left (treeInsert x right)

singleton 함수는 어떤 값과 두개의 빈 하위 트리를 가진 노드를 만들어줍니다. treeInsert 함수에서는 먼저 종료 조건을 정의하였습니다. 만약 빈 하위 트리를 만나면, 이것은 빈 트리를 대신해서 입력받은 값을 포함한 싱글톤 트리를 넣을 의미합니다. 종료조건에 매칭되지 않으면 몇가지 사항을 확인해야 합니다. 우선 넣을 노드가 루트 노드와 같은 경우, 동일한 트리를 리턴합니다. 넣을 노드의 값이 작으면 루트 노드와 오른쪽 하위 트리는 동일하게 리턴하고, 왼쪽 하위 트리는 새로운 값을 넣은 트리를 넣습니다. 넣은 노드의 값이 크면 반대로 오른쪽 하위 트리를 새로운 값을 넣은 트리로 대신합니다.

이제 트리안에 어떤 노드가 있는지 확인하는 함수를 만들어 보겠습니다. 리스트에서 어떤 요소를 포함하는지 검사할때, 빈리스트를 만나면 찾고있는 요소가 없는 것이므로 재귀를 종료하였습니다. 마찬가지로 여기에서도 찾고있는는 노드가 빈트리를 만나는 것을 종료조건으로 합니다. 만약 찾고있는 노드의 값이 루트노드와 같다면, 해당 노드가 찾고있는 노드가 될 것입니다. 찾고있는 노드의 값이 루트노드보다 작으면 왼쪽트리에서 찾고, 크면 오른쪽 트리에서 찾아야 합니다.

treeElem :: (Ord a) => a -> Tree a -> Bool
treeElem x EmptyTree = False
treeElem x (Node a left right)
    | x == a = True
    | x < a  = treeElem x left
    | x > a  = treeElem x right

이제 트리를 수동으로 만드는 대신 리스트로부터 트리를 만들어 보겠습니다. 이전에 리스트를 하나씩 검색하여 어떤 종류의 값을 리턴하는 것은 fold를 사용하여 구현될 수 있다는 것을 배웠습니다. 여기서는 빈트리에서 시작해서 리스트의 오른쪽에서부터 accumulator 트리안에 노드 뒤에 새로운 노드를 추가해나갈 것입니다.

ghci> let nums = [8,6,4,1,7,3,5]
ghci> let numsTree = foldr treeInsert EmptyTree nums
ghci> numsTree
Node 5 (Node 3 (Node 1 EmptyTree EmptyTree) (Node 4 EmptyTree EmptyTree)) (Node 7 (Node 6 EmptyTree EmptyTree) (Node 8 EmptyTree EmptyTree))

foldr에서 treeInsert는 folding 함수(트리와 리스트의 값을 입력받아서 새로운 트리를 리턴하는..)이고 EmptyTree는 초기값입니다. nums는 folding할 리스트입니다.

ghci> 8 `treeElem` numsTree
True
ghci> 100 `treeElem` numsTree
False
ghci> 1 `treeElem` numsTree
True
ghci> 10 `treeElem` numsTree
False

지금까지 살펴보았듯이 대수적 데이터 구조는 하스켈에서 매우 강력한 개념입니다. boolean값과 열거형에서부터 이진 검색 트리 이상의 것을 만드는데 사용할 수 있습니다.

results matching ""

    No results matching ""