先寬度標記 — Oleg Kiselyov 的解法

稍早一篇文章談到先寬度標記問題:

考慮如下的二元樹:

data Tree a = Node a (Tree a) (Tree a) 
            | Leaf a

試寫一個函數 bfl：如果 xs 是一個串流（stream, 即無限長的串列），bfl t xs 會在與樹的大小成線性比例的時間內，依先寬度的順序把 t 的節點一個個用 xs 標記。

這裡的樹和前文稍有不同，在外部節點上也有標記，這小差異並不重要。2000 年的 ICFP 中，Chris Okasaki 發表了一篇關於本問題的論文，並在上台前一天把這個問題丟給在場的人當作挑戰題。其他故事以及一些解法請參考前文。

幾天前 Oleg Kiselyov 寫信給我：

我參加了 Chris Okasaki 提出這個問題的那次 ICFP… 我花了整個晚上解這個問題，最後有了一個使用 skip list 的解答。第二天早上我把解答給 Chris Okasaki 看，他說：「我相信你是對的。可是，這是我看過最複雜的答案！」

咦？那真是太巧了。我連忙回信問他，當時他們是不是在會議室門口的外面，旁邊還有一堆人看著。因為我記得我當時也站在一旁聽，而且記得 Okasaki 的那句回答。那時我還不認識 Oleg 呢。世界真奇妙呀。

Oleg 這次趁著搭飛機與拜訪牛津的空檔，另做了個更簡潔的解答。乍看之下這是另一個分層式的解法，基本上是先把樹轉成串列的串列，加以標記之後，再轉回來。為了保存樹的形狀，串列存放的是這個型別：

data ZT a = LV a | NV a

內部節點被轉成 NV, 外部節點被轉成 LV. 例如這麼一棵樹：

tree1 = Node 1 (Node 2  (Leaf 3) 
                        (Node 4  (Leaf 5)  
                                 (Leaf 6)))
	       (Node 12 (Node 14 (Leaf 15) 
                                 (Leaf 16))
		        (Leaf 13))

會被轉成這樣的分層：

 [[NV 1],
  [NV 2,NV 12],
  [LV 3,NV 4,NV 14,LV 13],
  [LV 5,LV 6,LV 15,LV 16]]

這個動作由函數 bf_unzip 完成。反過來的轉換則由 bf_zip 負責，而 bfz_label 負責標記。完整程式在這裡：http://okmij.org/ftp/Haskell/BFN.hs

Oleg 說：

令我驚訝的是我並不需要直接使用佇列(queue)，也不用那個用兩個串列來實作佇列的技巧。佇列隱性地藏在 bf_unzip 函數中使用 foldr 的部份。只要用 fold 就可以了，所以我想你會有興趣。

也貼在這兒給大家看。