先寬度標記

考慮內部節點標記的二元樹:

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 時,我們用 xy, 並把兩棵子樹 tu 放到佇列最後面。標好的樹排在佇列 ws 之中,我們再把最後兩棵子樹取回來就可以了。看懂之後會覺得怎麼之前沒想到呢?

後來一篇談反函數的論文中我用本問題當作例子,焦點則是把這個演算法導出來。利用的性質是「先寬度標記是先寬度訪問的反函數再加上一個 zip」。最後寫道「為何當時大家想不到簡單的程式?因為沒學過我們的反函數定理!」當然,這是開玩笑的。此是後話不表。

階層式解法

不過,Okasaki 在 ICFP 提出挑戰時加上一個但書,「不要用很難的 lazy evaluation。」當場大家抗議聲四起,「為什麼不行?為什麼?」

原來更早之前 Geraint JonesJeremy Gibbons 已有了另一篇論文,把先寬度標記當作 foldzip 的推導練習,並使用 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。有了 spirallvlabel 的幫助,bfl 可以寫成:

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

循環引用程式

上面的程式中,我們看到一個函數的輸出又被餵給自己。這種循環引用程式是 non-strict 語言常用的技巧之一。

寫這種程式時,我們怎麼知道 ys 的計算不會陷入無窮迴圈?我們必須確定 ys 的每個元素會在被需要之前先算出來。有時這並不容易。

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

參考資料

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

Post a Comment

Your email is never published nor shared. Required fields are marked *

*
*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>