要素数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))

シンプルな問題でも本当に奥が深い．