On states

我想我發現一個比「functional languages 沒有 side effects」更好的說法：functional languages 沒有 implicit states。寫過一點 functional programs 的人都知道，很多概念仍然和 imperative programs 是對應的。例如 functional, tail-recursive fibonacci 和 imperative, iterative fibonacci 其實是同一件事情：

ffib : ℕ → ℕ → ℕ → ℕ
ffib 0 x y = y
ffib (suc n) x y = ffib n y (x + y)

（本來是要用 Haskell 寫的，可是 n + k patterns 最近又掀起一小波筆戰，很討厭 XD。）在 ffib 裡面，第一個 parameter 是 loop counter（順便一提，絕大部份的 for loops 都是 induction）、第二和第三個 parameter 就相當於對 x, y 兩個變數做 parallel assignment x, y = y, x + y。稍微追蹤一下 ffib 的求值過程，就能感覺到對應的 imperative program 該有的 states 一點不缺，只是 functional version 把所有 states 明確寫出來而已。更明顯的例子自然是 state monad，因為 monad structure 把 state 藏起來了，如果又用 do notation 寫的話，monadic code 一看就覺得根本是 imperative programs。

所以在 state 這件事上，functional languages 和 imperative languages 有時候其實是異曲同工。把全部的 states 都寫出來，就不會為了顧及 implicit states 而在推理轉換時絆手絆腳；但當 state 規模變大時，處理起來就不那麼順手了，此時 imperative programs 的專門語法反而比較方便。因此我想 functional langauges 最大的威力還是 "functions as first-class values"。不過這是後話了…

--
本來覺得很 trivial 不想寫，但還是寫一下好啦 XD。