考慮內部節點標記的二元樹:
data Tree a = Node a (Tree a) (Tree a)
| Null
目標是寫一個型別為 Tree a -> [b] -> Tree (a, b) 的函數 bfl。如果 xs 是一個串流（stream, 即無限長的串列），bfl t xs 會依先寬度（而非先深度）的順序把 t 的節點一個個用 xs 標記。例如:
t = Node 'a' (Node 'b'
(Node 'c' Null Null)
(Node 'd' Null Null))
(Node 'e'
(Node 'f' Null Null)
(Node 'g' Null Null))那麼 bfl t [0..] 的結果會是:
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))最後還有個附加條件：程式希望在與樹的大小成線性比例的時間內執行完畢。
這個函數有很多寫法。你會怎麼寫呢？如果你愛寫程式，強烈建議你在讀下去前先試試看。
先寬度訪問
如果問題是先寬度訪問（breadth-first traversal），大家都比較會寫：
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])標準的演算法是用一個佇列(queue), 每次把佇列中第一棵樹的標記抓出來，把兩個子樹放到後面，直到佇列空了為止。我們使用串列的語法，但假設 bfts 的輸入輸出都是佇列，而 ++ 的動作只花 O(1) 的時間。
但如果換成先寬度標記，許多人就不太會寫了。Chris Okasaki 在 2000 年的 ICFP 發表了一篇關於先寬度標記問題的論文，並在上台前一天把這個問題丟給在場的人當作挑戰題。Okasaki 的理想解答只需把先寬度訪問的程式稍加修改即可。但如他所料，許多人提出了千奇百怪的複雜程式。明明有個簡單的解，許多人卻想不到，必定有個思考上的盲點吧？後來他甚至「寫」了一篇只有圖、沒有文字的論文投到 Journal of Functional Programming，但似乎沒被採用。幾年後部落格大流行，這些圖也放到他的部落格上了。
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)我們仍使用一個佇列。遇到 Node y t u 時，我們用 x 標 y, 並把兩棵子樹 t 和 u 放到佇列最後面。標好的樹排在佇列 ws 之中，我們再把最後兩棵子樹取回來就可以了。看懂之後會覺得怎麼之前沒想到呢？
後來一篇談反函數的論文中我用本問題當作例子，焦點則是把這個演算法導出來。利用的性質是「先寬度標記是先寬度訪問的反函數再加上一個 zip」。最後寫道「為何當時大家想不到簡單的程式？因為沒學過我們的反函數定理！」當然，這是開玩笑的。此是後話不表。
階層式解法
不過，Okasaki 在 ICFP 提出挑戰時加上一個但書，「不要用很難的 lazy evaluation。」當場大家抗議聲四起，「為什麼不行？為什麼？」
原來更早之前 Geraint Jones 和 Jeremy Gibbons 已有了另一篇論文，把先寬度標記當作 fold 和 zip 的推導練習，並使用 lazy evaluation. Okasaki 不希望大家往那個方向去想。
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'')
函數 lvlabel （levelled labelling）的參數是一棵樹，和一個串流的串流 (a stream of streams)。用第一個串流來標樹的第一層，第二個串流標樹的第二層。除了傳回標好的樹，也傳回每層「剩下」的 串流。 舉例說明，前一節給的例子 t 可以畫成這樣：
a
/ \
b d
\ / \
c e f
/
g如果給的串流的串流是 xss = [[00, 01, 02...],[10, 11, 12....],[20,21,22..],...]，那麼 lvlabel t xss的結果畫成圖就是這樣:
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,...]但我們現在只有一個串流, 而不是 stream of streams. 我們需要有個函數把右邊「剩下」的串流再餵回左邊，使得 [01,02,03,..] 實際上就是 [10,11,12..]；[12, 13, 14,…] 實際上就是 [20,21,22,..]。這是 sprial 這個函數的工作:
spiral :: (a -> [b] -> (c, [b])) -> a -> b -> c
spiral f x y = x'
where (x', ys) = f x (y: ys)我們可以看到它把 f 輸出的 ys 又餵回給 f。有了 spiral 和 lvlabel 的幫助，bfl 可以寫成:
bfl :: Tree a -> [b] -> Tree (a, b)
bfl t xs = spiral lvlabel t xs循環引用程式
上面的程式中，我們看到一個函數的輸出又被餵給自己。這種循環引用程式是 non-strict 語言常用的技巧之一。
寫這種程式時，我們怎麼知道 ys 的計算不會陷入無窮迴圈？我們必須確定 ys 的每個元素會在被需要之前先算出來。有時這並不容易。
2008 年秋天我在仙台一次會議遇見 Conor McBride. 他提到想發展一套型別系統，描述串流的某個元素在何時被算出來並藉此論證這類程式的 productivity. 自然地他用了這個例子，我便想把這些老故事挖出來給台灣的朋友們看看。這是本文的由來，並充作本部落格的開幕文。
參考資料
- G. Jones and J. Gibbons. Linear-time breadth-first tree algorithms: an exercise in the arithmetic of folds and zips. Technical Report No. 71, Oxford University Computing Laboratory , 1993.
- C. Okasaki. Breadth-first numbering: lessons from a small exercise in algorithm design. The 5th International Conference on Functional Programming, pp. 131-136, 2000.
- S-C. Mu and R. S. Bird. Theory and applications of inverting functions as folds. In Science of Computer Programming Vol. 51 Special Issue for Mathematics of Program Construction 2002, pp. 87-116, 2003