Leaf에 label을 붙인 binary tree는 ..
data F a = B a a deriving (Show, Functor)
type T a = Free F a
(이를 위해서는 DeriveFunctor 확장을 켜야함)
leaf a = return a
node a b = warp (B a b)
(여기서 wrap은 Free 생성자를 한번더 추상화한 것. MonadFree 에 선언)
fullTree :: (MonadFree F m) => Int -> m String
fullTree 0 = leaf ""
fullTree n = do
s <- fullTree (n-1)
node (leaf (s ++ "1")) (leaf (s ++ "0"))
root부터 지그재그(왼쪽오른쪽왼쪽..)로 내려가서 맨끝 leaf찾는 함수 zigzag
zigzag :: T a -> a
zigzag = zig
where zig (Pure a) = a
zig (Free (N a b)) = zag a
zag (Pure a) = a
zag (Free (N a b)) = zig b
사실 fullTree n의 n에 linear하게 동작해야겠지만 zigzag (fullTree n)은 quadratic 복잡도로 동작한다. 이유는 fullTree로 생성되는 트리 구조가 leaf노드를 확장해나가는 방식이 painter 알고리즘과 같기 때문이다.
data F a = B a a deriving (Show, Functor)
type T a = Free F a
(이를 위해서는 DeriveFunctor 확장을 켜야함)
leaf a = return a
node a b = warp (B a b)
(여기서 wrap은 Free 생성자를 한번더 추상화한 것. MonadFree 에 선언)
fullTree :: (MonadFree F m) => Int -> m String
fullTree 0 = leaf ""
fullTree n = do
s <- fullTree (n-1)
node (leaf (s ++ "1")) (leaf (s ++ "0"))
> (fullTree 3) :: T String
Free (N (Free (N (Free (N (Pure "111") (Pure "110"))) (Free (N (Pure "101") (Pure "100"))))) (Free (N (Free (N (Pure "011") (Pure "010"))) (Free (N (Pure "001") (Pure "000"))))))
root부터 지그재그(왼쪽오른쪽왼쪽..)로 내려가서 맨끝 leaf찾는 함수 zigzag
zigzag :: T a -> a
zigzag = zig
where zig (Pure a) = a
zig (Free (N a b)) = zag a
zag (Pure a) = a
zag (Free (N a b)) = zig b
사실 fullTree n의 n에 linear하게 동작해야겠지만 zigzag (fullTree n)은 quadratic 복잡도로 동작한다. 이유는 fullTree로 생성되는 트리 구조가 leaf노드를 확장해나가는 방식이 painter 알고리즘과 같기 때문이다.
그림에서처럼 leaf노드가 확장될 때마다 루트까지의 부모 노드를 모두 새로 생성한다.
반면 zigzag (improve (fullTree n)) 은 linear하게 동작한다.
improve :: Functor f => (forall m. MonadFree f m => m a) -> Free f a
이때 fullTree가 선택하는 m은 Free F가 아니라 Codensity (Free F) 이다.
이에 따라 zigzag (fullTree N)과 zigzag (improve (fullTree N))의 실행속도를 비교해보면 다음과 같다.
댓글 없음:
댓글 쓰기