# 先寬度標記

``````data Tree a = Node a (Tree a) (Tree a)
| Null
``````

``````t = Node 'a' (Node 'b'
(Node 'c' Null Null)
(Node 'd' Null Null))
(Node 'e'
(Node 'f' Null Null)
(Node 'g' Null Null))``````

``````    Node ('a',0) (Node ('b',1)
(Node ('c',3) Null Null)
(Node ('d',4) Null Null))
(Node ('e',2)
(Node ('f',5) Null Null)
(Node ('g',6) Null Null))``````

### 先寬度訪問

``````bft : Tree a -> [a]
bft t = bfts [t]

bfts [] = []
bfts (Null : ts) = bfts ts
bfts (Node y t u : ts) = y : bfts (ts ++ [t,u])``````

Okasaki 的解法大約是這樣：

``````bfl xs t = head (bfls xs [t])

bfls _ [] = []
bfls xs (Null : ts) = Null : bfls xs ts
bfls (x : xs) (Node y t u : ts) = Node (y,x) v w : ws'
where ws = bfls xs (ts ++ [t, u])
(ws', v, w) = (init (init ws), last (init ws), last ws)``````

### 階層式解法

Jones & Gibbons 的程式是分層運作的。先看下述的函數:

``````lvlabel :: Tree a -> [[b]] -> (Tree (a,b), [[b]])
lvlabel Null yss = (Null, yss)
lvlabel (Node x t u) ((y: ys): yss) =
let (t', yss') = lvlabel t yss
(u', yss'') = lvlabel u yss'
in (Node (x,y) t' u', ys : yss'')
``````

``````     a
/   \
b      d
\     / \
c   e   f
/
g``````

``````      a,00                [01,02,03,...]
/        \
b,10       d,11         [12,13,14,...]
\        /    \
c,20   e,21   f,22    [23,24,25,...]
/
g,30        [31,32,33,...]``````

``````spiral :: (a -> [b] -> (c, [b])) -> a -> b -> c
spiral f x y = x'
where (x', ys) = f x (y: ys)``````

``````bfl :: Tree a -> [b] -> Tree (a, b)
bfl t xs = spiral lvlabel t xs``````

### 循環引用程式

2008 年秋天我在仙台一次會議遇見 Conor McBride. 他提到想發展一套型別系統，描述串流的某個元素在何時被算出來並藉此論證這類程式的 productivity. 自然地他用了這個例子，我便想把這些老故事挖出來給台灣的朋友們看看。這是本文的由來，並充作本部落格的開幕文。