本日新知

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

本日最實用：difference lists。這是在 Edward Kmett 的〈A Sort of Difference〉看到的。Difference lists 是以 functions 表示 lists，而能得到常數時間的 append 和 snoc 操作。（當然 cons 也仍然只花常數時間。）很多常見的東西如 (++) = foldr ((.) . (:)) id 和 revcat = (++) . 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。