2008/07/29

本日新知

腦袋重新進入工作狀態,所以來消一點 "interesting posts"。(是的,我會放在那裡一般是因為我日後才要看 XD。)

本日最實用:difference lists。這是在 Edward Kmett 的〈A Sort of Difference〉看到的。Difference lists 是以 functions 表示 lists,而能得到常數時間的 append 和 snoc 操作。(當然 cons 也仍然只花常數時間。)很多常見的東西如 (++) = foldr ((.) . (:)) idrevcat = (++) . reverse 都可以視為傳回 difference list 的函式。

本日最新奇:automatic differentiation。這是從單中杰老師的〈Differentiating Regions〉看來的,文內另外有一些連結連往其他人的 blog posts。一般求導數大概就是符號操作(先從 f(x) 的型式算出 f'(x) 的型式再代值)或是數值近似(算牛頓商 (f(x + h) - f(x)) / h,其中 h 是個適當的小數字),而 automatic differentiation 藉著一套擴充實數系的新數系 "dual numbers" 引進物理系常用的無窮小估算(例如 (x + dx)^2 = x^2 + 2x dx + dx^2 = x^2 + 2x dx),可以精確快速方便地求得函數在某一點的導數。這樣的手法在 Haskell 和 C++ 這種支援 parametric polymorphism 和 operator overloading 的語言下可以實作得相當漂亮。我第一眼看到就大呼神奇,值得來研究一下。

--
都和 "difference" 有關係 XD。

Labels:

<< 回到主頁