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

문제 수정본 https://gall.dcinside.com/mgallery/board/view/?id=github&no=31236&page=1


이번 문제는 재귀에 어울리는 알고리즘을 어떻게 루프랑 스택으로 작성하는지가 관건이었음.

직접 머리써서 풀어도 되지만, 나는 일단 재귀 알고리즘을 작성하고 루프로 바꾸는 방법을 소개하려고 함.

fold로 설명하겠음.


문제에 있지만 Tree의 정의는 이거고

1data Tree a = Node a [Tree a] deriving (Eq, Show)


fold의 기본적인 구현은 이렇게 됨

1 2 3-- naive implementation using recursion fold :: (a -> [b] -> b) -> Tree a -> b fold f (Node x ts) = f x (map (fold f) ts)


우선 고차함수 상태로는 재귀가 어떻게 일어나는지 알 수 없으니, map의 정의를 인라이닝함

1 2 3 4 5 6 7-- clarify mutual recursion foldMut :: (a -> [b] -> b) -> Tree a -> b foldMut f = go1 where go1 (Node x ts) = f x (go2 ts) go2 [] = [] go2 (t:ts) = go1 t : go2 ts

그러면 fold는 go1과 go2 두개 함수의 mutual recursion으로 표현이 됨.


그런데 go2는 go1, go2를 모두 재귀호출 하지만 go1은 go2만을 재귀호출하기 때문에 go1을 다시 인라이닝하면 서로재귀가 사라진다.

1 2 3 4 5 6-- inlining foldInline :: (a -> [b] -> b) -> Tree a -> b foldInline f = (Node x ts) -> f x (go ts) where go [] = [] go (Node x ts' : ts) = f x (go ts') : go ts

서로재귀를 없애는게 필수적이지는 않지만 없애면 뒤에 과정이 더 단순해짐.


이제 중요한 부분인데, CPS(Continuation-passing style) 변환을 해야함

1 2 3 4 5 6 7 8 9-- apply CPS conversion foldCPS :: (a -> [b] -> b) -> Tree a -> b foldCPS f = (Node x ts) -> f x (go ts id) where go [] k = k [] go (Node x ts' : ts) k = go ts' $ ys' -> go ts $ ys -> k (f x ys' : ys)

https://en.wikipedia.org/wiki/Continuation-passing_style

CPS 변환이 뭔지를 직접 설명하긴 벅차서 생략하겠음.


CPS 변환은 재귀 알고리즘을 명령형 스타일로 바꿀때 매우 중요한 변환임.

원래 재귀 알고리즘에는 '평가순서'가 정해져있지 않음.

예를 들어 다음 부분에서

1 go (Node x ts' : ts) = f x (go ts') : go ts

go ts' 이랑 go ts 중 어느게 먼저 계산되는지는 언어의 평가전략에 따라 다름.


하지만 CPS 변환을 수행한

1 2 3 4 go (Node x ts' : ts) k = go ts' $ ys' -> go ts $ ys -> k (f x ys' : ys)

에서는 반드시 go ts' 이 먼저 수행됨.


반면에 CPS변환을 다음처럼 하면

1 2 3 4 5 6 7 8foldCPS :: (a -> [b] -> b) -> Tree a -> b foldCPS f = (Node x ts) -> f x (go ts id) where go [] k = k [] go (Node x ts' : ts) k = go ts $ ys -> go ts' $ ys' -> k (f x ys' : ys)

go ts 가 먼저 계산되고, 후에 go ts'이 계산됨.


CPS 변환된 코드의 또 다른 특징은 tail recursive 하다는 점임.

원래 foldMut/foldInline 함수는 tail recursion이 아니었지만 CPS변환을 거치면 tail recursion 꼴로 바뀜.

그러니 여기까지하면 문제에서 요구한 "루프 혹은 꼬리재귀만 사용"조건은 만족이 됨.

하지만 go의 두번째 인자인 continuation k가 함수기 때문에 go는 고차함수가 되는데,

로우레벨 언어에서는 고차함수가 없기 때문에 이런 방식을 C같은 언어에서 쓰려면 추가적인 변환이 필요함.


여기서 필요한게 "defunctionalization"임

https://en.wikipedia.org/wiki/Defunctionalization

defunctionalization은 함수를 데이터 타입으로 표현하는 테크닉임.

이걸 사용하면 인자로 받는 continuation이 함수가 아닌 데이터로 바뀌기 때문에 고차함수 없이 구현할 수 있게 됨.


우선 defunctionalization을 적용하기에 앞서서 continuation들을 명시적으로 바인딩해서 정리함

1 2 3 4 5 6 7 8 9 10 11 12 13-- factor out continuations foldCPS' :: forall a b. (a -> [b] -> b) -> Tree a -> b foldCPS' f = (Node x ts) -> f x (go ts (id :: [b] -> [b])) where go :: forall r. [Tree a] -> ([b] -> r) -> r go [] k = k [] go (Node x ts' : ts) k = go ts' (kont1 x ts k) kont1 :: forall r. a -> [Tree a] -> ([b] -> r) -> [b] -> r kont1 x ts k = ys' -> go ts (kont2 x ys' k) kont2 :: forall r. a -> [b] -> ([b] -> r) -> [b] -> r kont2 x ys' k = ys -> k (f x ys' : ys)

kont1, kont2 가 받은 인자중 x ts k, x ys' k 는 해당 람다식이 캡쳐한 변수들을 명시적으로 바인딩한거임.

go, kont1, kont2 의 리턴타입은 r 이지만, 실제로 사용될 때 continuation 인자로 id :: [b] -> [b] 를 넘기기 때문에, r은 [b]가 됨.


이제 각각의 continuation들을 표현하는 데이터 타입을 정의함.

1data Kont a b = Id | Kont1 a [Tree a] (Kont a b) | Kont2 a [b] (Kont a b)

Kont a b 라는 타입은 [b] -> [b] 타입의 함수를 표현하는 데이터 타입임. (아까 말했듯이 [b] -> r 에서 r = [b] 라서 [b] -> [b] 가 된거임)

foldCPS' 을 보면 세개의 continuation이 있음 (id, kont1, kont2)

이 각각의 continuation들에 대해서 case를 만들고 continuation이 캡쳐하는 변수들을 담는 field를 선언하면 됨.

예를 들어서 kont1 은 (x :: a), (ts :: [Tree a]), (k :: [b] -> r) 이렇게 세개의 변수를 캡쳐하기 때문에 Kont1 a [Tree a] (Kont a b) 로 정의가 된거임.


이 Kont 타입을 사용해서 continuation인자를 바꾸면 코드가 아래처럼 바뀜

1 2 3 4 5 6 7 8 9 10 11 12 13 14-- defunctionalization data Kont a b = Id | Kont1 a [Tree a] (Kont a b) | Kont2 a [b] (Kont a b) foldDefunc :: forall a b. (a -> [b] -> b) -> Tree a -> b foldDefunc f = (Node x ts) -> f x (go ts Id) where go :: [Tree a] -> Kont a b -> [b] go [] k = apply k [] go (Node x ts' : ts) k = go ts' (Kont1 x ts k) apply :: Kont a b -> [b] -> [b] apply Id ys = ys apply (Kont1 x ts k) ys' = go ts (Kont2 x ys' k) apply (Kont2 x ys' k) ys = apply k (f x ys' : ys)

원래 go에서 kont1을 continuation으로 넘겼던 코드가 Kont1 이라는 데이터를 넘기는걸로 바꼈음.

그리고 apply가 새로 생겼는데, 이 함수가 바로 Kont 타입을 해석하는 함수임.

Kont a b 라는 타입을 [b] -> [b] 로, 즉 진짜 함수로 바꾸는거지.


재밌는 점은 Kont를 리스트로 바꿀 수 있다는거임.

Kont1, Kont2가 각각 Kont a b 타입의 필드를 하나씩만 가지기 때문에 Kont는 선형적인 타입이고,

Id가 empty list의 역할을 해서 리스트로 표현이 됨.

이걸 이용해서 코드를 작성하면 아래같은 코드가 나옴.

1 2 3 4 5 6 7 8 9 10 11 12 13 14-- Kont using list type Kont' a b = [Either (a, [Tree a]) (a, [b])] foldDefunc' :: forall a b. (a -> [b] -> b) -> Tree a -> b foldDefunc' f = (Node x ts) -> f x (go ts []) where go :: [Tree a] -> Kont' a b -> [b] go [] k = apply k [] go (Node x ts' : ts) k = go ts' (Left (x, ts) : k) apply :: Kont' a b -> [b] -> [b] apply [] ys = ys apply (Left (x, ts) : k) ys' = go ts (Right (x, ys') : k) apply (Right (x, ys') : k) ys = apply k (f x ys' : ys)

go, apply는 리스트 인자를 추가로 받는 mutual tail recursive function이 됐음.

근데 함수형 언어의 cons list는 사실 스택이랑 비슷함. head에서만 push/pop이 가능하니까.

리스트가 사실 콜스택이랑 똑같은 역할을 하는거지.


잘 알려져있듯이 tail recursive function은 loop로 쉽게 바꿀 수 있음. (tail call optimization)

이것도 한번 직접 해보자. 난 러스트로 만들어봤음

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62#[derive(PartialEq, Debug)] pub struct Tree<A> { value: A, children: Vec<Tree<A>>, } enum KontElem<'a, A, B> { Kont1(&'a A, &'a [Tree<A>]), Kont2(&'a A, Vec<B>), } impl<A> Tree<A> { pub fn fold<B, F>(&self, f: F) -> B where F: Fn(&A, Vec<B>) -> B, { let mut stack: Vec<KontElem<A, B>> = vec![]; let mut ts: &[Tree<A>] = &self.children; let ys = 'main_loop: loop { // go while let Some((ts_head, ts_tail)) = ts.split_first() { stack.push(KontElem::Kont1(&ts_head.value, ts_tail)); ts = &ts_head.children; } // apply let mut ys_reversed: Vec<B> = vec![]; loop { if let Some(kontelem) = stack.pop() { match kontelem { KontElem::Kont1(x, ts_) => { ts = ts_; let ys = { ys_reversed.reverse(); ys_reversed }; stack.push(KontElem::Kont2(x, ys)); break; } KontElem::Kont2(x, ys) => ys_reversed.push(f(x, ys)), } } else { ys_reversed.reverse(); break 'main_loop ys_reversed; }; } }; f(&self.value, ys) } pub fn map<B, F>(&self, f: F) -> Tree<B> where F: Fn(&A) -> B, { self.fold(|x, ys| Tree { value: f(x), children: ys, }) } }


map을 실행 해보면 예상한대로 잘 동작함!


https://gist.github.com/damhiya/c3db201dae7bb9a70bc0072be9a5ab93

코드 gist로 보고싶으면 여기로


참고로 이 글에서 설명한 defunctionalization은 여기서 훨씬 자세히 알려줌