函數式編程能否解決所有經典的演算法問題？

01-03

最近學Scala剛起步，寫代碼時總是自然的先用指令式編程的思維方式設計，然後想方設法的再用函數式編程中的概念替換。比如用recursive function call代替一些while loop，用map/reduce代替某一些場合下的for loop。但是有一些場合也會不知道怎麼替換。
姑且不論這樣寫Scala對不對（多半並不對...），首先就有一個疑問，是不是所有的演算法都可以用函數式編程實現，比如一些圖論的演算法（最短路徑， minimum spanning tree等等）？

http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki-ebook/dp/B00AKE1V04

題主你應該看這本書。函數式語言有自己獨有的數據結構，《演算法導論》上面的演算法基本廢掉，只能留下指導思想了。所以不是什麼概念直接替換一下就可以的，你應該重頭學。

這取決於你說的「解決」是什麼意思。

純函數式語言實現的計算模型是 λ-calculus，過程式語言實現的是圖靈機（這裡暫時忽略圖靈機和隨機存取機的差別）。λ-calculus 和圖靈機在可計算性上是等價的，但是他們的等價性也就止步於可計算性了。傳統的演算法書大部分是以圖靈機和過程式語言講解演算法，原因是圖靈機模型里複雜度很好計算，讀寫的次數，存儲數據占的空間都是可以精確衡量的。而在 λ-calculus 里一個 β-reduction 消耗的時間單位，一個函數佔用的空間都缺乏有現實意義的衡量標準。2014 年有篇論文（http://arxiv.org/abs/1405.3311）指出了像 P、NP、EXP 這樣大粒度的時間複雜度等級在 λ-calculus 里也是可以定義的，但是 $O(n^2)$ 和 $O(nlog{n})$ 之類在 λ-calculus 里就沒法定義了。

所以如果你說的「解決」是指可以計算的話，那麼可以解決的演算法問題在兩種情況下都是一樣的。但在純函數式語言里解決同樣問題的複雜度就取決於這個語言的具體實現了。很有可能兩個複雜度一樣的演算法，用函數式語言實現後運行起來性能特徵就很不一樣了。畢竟物理世界的計算機都更接近於圖靈機的模型，不管拿什麼語言寫的程序，最終都是在這個模型下運行的。你可以把函數式語言的實現理解為一個解釋器/編譯器把 λ-calculus 的程序翻譯成圖靈機的程序。

我的結論是：可以，因為圖靈完備性。但函數式編程對遞歸數據結構的演算法問題效果較好，對需保存狀態的以及需要隨機地址存取的數據結構效果較差。因為函數式編程的演算法是遞歸的，遞歸數據結構與遞歸演算法天生就很相配。

演算法與數據結構是分不開的。數據結構的核心是引用與解引用。

例如樹結構，struct tree_node{ parent, left, right }，left與right是兩個從干到枝的引用，parent是從枝到乾的引用。對一般的操作，遞歸都很方便。但是紅黑樹就有麻煩了，因為有狀態，而不是簡單的引用與解引用的問題。改變狀態，在函數式編程特別是純函數式編程裡面就是天大的事，因為可能是一個對象的生滅。

再舉例看list數據結構和map、filter這樣的高階函數。map、filter需要利用list的遞歸數據結構：struct list{ car, cdr }。map和filter的操作是先解引用car用一個函數f操作，把剩餘cdr部分和map或filter打包到遞歸函數裡面。但是如果要隨機存取呢？比如直接取第100個元素？如果不改變list結構的底層（指的是list的定址方式由遞歸改成隨機定址），那麼就是非常困難的。map結構的key如果不能隨機定址，map就沒有存在的必要了。

最後舉一個例子：丘奇數。丘奇數是遞歸定義的自然數，加減乘除靠遞歸演算法實現。實在不如小學生的九九表來得直接。

回到問題本身，若要強行用遞歸演算法解決一切演算法問題，需要先針對問題設計一個好的遞歸數據結構。比如紅黑樹問題，也許轉變成2-3-4樹更方便一點？（猜測）

為什麼有這麼大的區別，我覺得因為從彙編碼的隨意goto到命令式的if/else/while，再到函數式的遞歸，抽象的概念越來越清晰，但是威力越來越受限制。人理解起來容易，但機器會覺得被綁住了手腳。對於確定的演算法，最快的是專用集成電路ASIC，最慢的是CPU和編程語言。

可以但不是很合適。

如果追求immutable的話，各種狀態機會寫得很蛋疼，不過最後還是能寫出來的。

推薦@vczh那本書

從lambda calculus和圖靈機的等價性來說，顯然是可行的。可問題是值得這樣去做么？FP帶來的一個很大的優勢是便於進行多線程操作，而事實上，之前學的很多演算法，比如dijkstra,prim,kruskal,tarjan這一系列基於DFS的圖論演算法都是完全sequencial的。對於這些演算法，用FP寫既不方便，又不高效。由於沒有變數，你需要把所有的副作用全部打包在函數的參數中，並以tuple的形式返回結果，這種邏輯上的轉換其實對你對FP以及演算法本身基本是沒啥大用的，不過給你繞了個大圈子。如果不信的話可以試試看在FP裡面寫一遍tarjan，迭代器的設計就可以累死人了2333。但是個人認為FP還是很適合去寫一些數據結構的，pattern match的特性真的能省不少事，所以總而言之，FP雖好，但有些不適合FP寫的演算法也彆強求自己，寫出來真是一包氣lol

lz可以試試用純函數式語言實現一個dijkstra+斐波那契堆，然後你就會呵呵一整天了。

所以各種標榜無副作用的純函數式語言，最主要的用途就是寫paper。

大多數是吧，看《演算法導論》里基本上所有的演算法都是以遞歸的方式書寫的，如果以函數式方式寫感覺要方便很多，個人最近正在嘗試使用C++和函數式語言haskell寫一些演算法。感覺函數式寫法要舒服很多。就說插入排序，歸併排序和快速排序吧，用指令式的寫法不光要思考演算法本身的遞歸結構，還有就是用數組下標的形式來實現這些演算法（個人感覺後面這一步驟是比排序演算法本身更難的部分，而且更容易出各種小bug），但是用haskell直接把演算法導論上的概念演繹玩就將排序實現了。感覺就像在做數學題一樣。

http://www.cs.cmu.edu/~15210/schedule.html

CMU 15210 用 sml實現了圖論的演算法，動態規劃，等等等等

所有這些計算模型的結果，從某種角度講，都是等價的，而且和泛式的馮諾伊曼機器，即數字計算機是等價的，這也隱含的說明了這樣一個結果，就是任何一個系統的結果都可能等價於另一個系統的結果，而任何一個系統都可以用另一個系統來模擬，然後lambda的創始人，Church這位數學家從理論上推想，所有對於計算的描述都是等價的，但是無法被證明，雖然如此，我們看到lambda計算能夠在數字計算機上實現的，這也許就是一個事實上的例子。

如果題主指的「演算法」就是「能行過程（Effective method）」的話，那麼根據丘奇圖靈論題（Church）任何一種圖靈完備的語言都能實現。

PS:題主可以看一點關於可計算性理論和形式語言的知識。

很有用，不然為何 java 要支持 lambd ？我就看看，最近想用函數式實現圖論演算法(呵呵)

erlang寫個堆排序

函數就是撿現成,資料越多越趁手.演算法就是費腦筋,程序沒編完,腦細胞就得先死一半,反正很沒效率就是了.