2008/01/20

神奇的摺疊融合

27 篇 paper 裡面第一個選上的是 Jeremy Gibbons 的〈A Pointless Derivation of Radix Sort〉。Gibbons 用的 specification 是一般「先用 most significant field 排序,若一樣再用 second most significant field 排序,一直往下排到 least significant field」的排法。接著 Gibbons 用一些技巧把 specification 整理成 point-free style 之後(這似乎才是 paper 的重點 XD),就可以用 fold-fusion 把原本的程式推演得「倒反」過來,先用 least significant field 排一排,再用 second least significant field 排,一直往上排到 most significant field。不只這樣,stability 的要求就出現在 fusion condition 裡面!真是太神奇了!

--
裡面到底發生什麼事還要再看一看 XD。

Labels: