費氏數怎麼算?
只需 O(log n) 個遞迴呼叫的費氏數演算法是怎麼來的?會比「公式解」快嗎?
只需 O(log n) 個遞迴呼叫的費氏數演算法是怎麼來的?會比「公式解」快嗎?
Haskell 語言的新標準 Haskell 2010 已在七月六日出爐了。
我有大約 25 分鐘的時間和同學們介紹函數程式演算. FLOLAC ’10 的同學少部份學過 Haskell 或其他函數語言,大部份只在一週前學了三小時的 OCaml, 寫了一些程式作業,但對 fold 之類的抽象觀念可能還難以掌握。
一個算式的語意成了「拿一個環境,傳回一個整數」的函數。的確,既然算式算成的那個整數必須由環境決定,算式其實不能看作一個數子,而應該是從環境到整數的函數才對。
函數 return 把一個型別為 a 的值「提升」到 m a;x >>= f 大致上的意思是執行 x 代表的運算,如果得到一個型別是 a 的值,把他傳給 f. 結果的型別是 m b.
Erik Meijer 正在微軟社群 Channel 9 上發佈一系列十三集的教學影片 Functional Programming Fundamentals,講解函數編程。第一集在第一天就達到了一萬次點閱量,兩週內得到十萬次點閱。
函數語言程式有比較好的數學性質,我們可用來對程式做各種推論和操作。
咦?那真是太巧了。當時我也站在一旁聽,而且記得 Okasaki 的那句回答。那時我還不認識 Oleg 呢。世界真奇妙呀。
三個函數都同樣地把串列從左至右走訪一遍,差別僅在碰到串列結尾時分別傳回不同的值,並用不同的運算元處理遞迴呼叫的結果。我們能不能讓這三個函數共用同一個定義呢?
由指令語言的觀點看函數語言,注意到的第一件事情是「函數語言裡面不可以改變數的值」。於是大家難免覺得奇怪,這怎麼會是個優點呢?自廢武功去掉一個功能,會有什麼好處呢?