https://gall.dcinside.com/mgallery/board/view/?id=github&no=31215&page=1

원래 문제


문제로 낼 함수 선정을 잘못해서 난이도 조절을 실패 했는데; 이번엔 적당한거 가져왔다고 생각함


일단 Tree 라는 타입은 그냥 자식 노드에 갯수 제한이 없는 평범한 트리구조고, 다음처럼 정의할 수 있음

data Tree a = Node a [Tree a]

하스켈

struct tree { int value; int child_num; tree *childs; };

C (노드에 저장된 값이 value고, childs 포인터는 child_num 갯수만큼의 트리를 포인터로 들고있음)

struct Tree<A> { value : A, childs : Vec<Tree<A>>, }

러스트


문제는 다음 함수들을 재귀 없이 루프만 사용해서, 혹은 꼬리재귀만 사용해서 구현하는 거임

1. toList

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

이게 첨 문제였는데, 너무 쉬워서 다른 함수 가져옴


2. mapTree

mapTree :: (a -> b) -> Tree a -> Tree b mapTree f (Node x ts) = Node (f x) (map (mapTree f) ts)

트리의 각 원소에 함수 f를 적용한 새로운 트리를 만드는 함수임. 리스트에 대한 map 함수의 트리 버전임.

중요한건, mapTree는 트리의 구조를 보존해야 함.


예를들어 3을 더하는 함수를 인자로 넘기면 각각의 원소가 3만큼 증가하고, 구조가 똑같은 트리가 나옴

>> mapTree (x -> x + 3) (Node 0 [Node 1 [Node 2 []], Node 3 [Node 4 [], Node 5 []], Node 6 []]) Node 3 [Node 4 [Node 5 []], Node 6 [Node 7 [], Node 8 []], Node 9 []]


3. foldTree

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

foldTree가 mapTree의 상위호환 함수긴 한데, 이해하기 까다롭기도 하고 mapTree 만으로도 하고 싶은 얘기는 다 할 수 있어서 이거는 풀어보고 싶은 사람만 푸는걸로 하겠음



문제 이상하게 내서 미안함