Rose tree는 임의의 갯수의 자식 노드를 가질 수 있는 트리 구조임.


<각 노드에 정수를 저장한 rose tree의 예시>

자식 노드가 0개라면 leaf가 되는거고, 1개 이상이라면 internal node가 되는셈.


Rose tree는 하스켈과 러스트에서 각각 아래와 같이 정의할 수 있음

data Tree a = Node a [Tree a]struct Tree<A> { value : A, childs : Vec<Tree<A>>, }


이제 이 트리의 순회를 생각해보자. rose tree의 원소들을 preorder로 순회하여 리스트로 만드는 함수는 다음과 같이 구현할 수 있음.

toList :: Tree a -> [a] toList (Node x ts) = x : (ts >>= toList)

혹은

toList :: Tree a -> [a] toList (Node x ts) = x : concatMap toList ts

여기서 concatMap은 flatMap이라고도 불리는 함수이고, 다음과 같이 정의됨

concat :: [[a]] -> [a] map :: (a -> b) -> [a] -> [b] concatMap :: (a -> [b]) -> [a] -> [b] concatMap f xs = concat (map f xs)


이제 테스트를 해보면

t1 :: Tree Int t1 = Node 1 [ Node 2 [ Node 3 [ Node 4 [] , Node 5 [] ] , Node 6 [] ] , Node 7 [ Node 8 [] , Node 9 [] ] , Node 10 [ Node 11 [ Node 12 [] ] , Node 13 [ Node 14 [] ] , Node 15 [] ] ] >> toList t1 [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]

리스트가 잘 나옴.

보면 알겠지만, 재귀 호출과 고차함수를 활용하면 toList를 아주 쉽게 구현할 수 있음.


하지만 이번 문제는 재귀와 고차함수를 사용하지 않고 트리 순회함수 toList를 구현하는 것임.

단, 함수형 언어의 경우 재귀를 전혀 사용하지 않고서는 프로그래밍이 불가능 하므로 꼬리재귀는 허용함.


스택을 사용해서 재귀호출 없이 이진트리를 순회하는 알고리즘이 있으니 이걸 변형하거나

재귀 알고리즘을 먼저 짠 다음에 루프로 변환하면 됨.


#### 추가문제 ####

 toList는 너무 쉽게 풀려서 추가문제를 내겠음.


fold :: (a -> [b] -> b) -> Tree a -> b fold f (Node x ts) = f x (map (fold f) ts)

fold 함수를 꼬리재귀 혹은 루프를 사용해서 구현하기.


참고로 fold로 toList를 구현할 수 있음

fold (λ x ys -> x : concat ys) t == toList t

나는 fold에서 쓸 수 있는 방식으로 toList 구현하고서 문제로 낸건데, toList에서만 되는 더 쉬운 방법을 미처 생각을 못했음.