要素数nの二分木を最悪計算量O(n)でリストへと平坦化 (flatten) する方法を4つ紹介する.
二分木は次のものを使う.
definition
data Tree a = Leaf | Node (Tree a) a (Tree a)
実験する場合は,次を使うといいと思う.
experiment
lefttree, righttree, perfecttree :: Int -> Tree Int
lefttree 0 = Leaf
lefttree n = Node (lefttree (n-1)) n Leaf
righttree 0 = Leaf
righttree n = Node Leaf n (righttree (n-1))
perfecttree 0 = Leaf
perfecttree n = Node (perfecttree (div n 2)) n (perfecttree (div n 2))
bash
> length $ flatten $ righttree 100000
100000
> length $ flatten $ lefttree 100000
100000
> length $ flatten $ perfecttree 100000
131071
まずは愚直解.最悪計算量は,木が完全に左に偏っている場合で O(n^2).
naive
flatten :: Tree a -> [a]
flatten Leaf = []
flatten (Node l x r) = flatten l ++ [x] ++ flatten r
ではさっそく,最悪計算量がO(n)である実装を見ていこう.
1番目は,差分リストを使う方法.
dlist
flatten :: Tree a -> [a]
flatten t = toList (go t)
where
go :: Tree a -> DList a
go Leaf = fromList []
go (Node l x r) = go l ++* fromList [x] ++* go r
type DList a = [a] -> [a]
fromList :: [a] -> DList a
fromList xs = (xs ++)
toList :: DList a -> [a]
toList dxs = dxs []
(++*) :: DList a -> DList a -> DList a
(++*) = (.)
2番目は,蓄積変数を使う方法.本質的には差分リストを使う方法と変わらないが,オーソドックスなテクニックだといえる.山本和彦氏がTwitterで教えてくださった.
accum
flatten :: Tree a -> [a]
flatten t = go t []
where
go Leaf xs = xs
go (Node l x r) xs = go l (x : go r xs)
3番目は,差分リストを脱関数化する方法.http://h2.jaguarpaw.co.uk/posts/demystifying-dlist/ に載っていた.
demystify
flatten :: Tree a -> [a]
flatten t = toList (go t)
where
go :: Tree a -> TList a
go Leaf = fromList []
go (Node l x r) = go l ++* fromList [x] ++* go r
data TList a = Tip [a] | Branch (TList a) (TList a)
fromList :: [a] -> TList a
fromList = Tip
toList :: TList a -> [a]
toList (Tip xs) = xs
toList (Branch (Tip xs) t) = xs ++ toList t
toList (Branch (Branch l r) t) = toList (Branch l (Branch r t))
(++*) :: TList a -> TList a -> TList a
(++*) = Branch
4番目は,不思議な方法.おそらく一番美しい方法.3番目をヒントに思い付いた.O(n)になることを確認してほしい.
wonder
flatten :: Tree a -> [a]
flatten Leaf = []
flatten (Node Leaf x t) = x : flatten t
flatten (Node (Node l x r) y t) = flatten (Node l x (Node r y t))
シンプルな問題でも本当に奥が深い.