先寬度標記 — 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 就可以了,所以我想你會有興趣。

也貼在這兒給大家看。

This entry was posted in 計算算計 and tagged , , . Bookmark the permalink. Post a comment or leave a trackback: Trackback URL.

One Comment