為什麼lists在functional programming里很重要？

01-28

這樣來看和arrays generic collections相比lists好像並沒有什麼優勢？而且似乎所有支持functional paradigm的語言里lists都有很重要的地位？

謝邀, 下面的list不是指ADT那種list, 特指FP中的immutable的list.

FP語言的鼻祖Lisp已經證明裡Lisp里的List是種表達能力很強的數據結構. F#, Haskell, Racket這些函數式編程語言更加強調不變性, 對數據的處理通常都是通過變換而不是in place做修改, 用index訪問元素這個操作會提供但是只會用在性能要求不高的場合.

性質上List是個monoid, 至於monoid 什麼作用可以參考為什麼haskell里需要monoid , 而且, List 是一個表示"可能性"的monad, List Comprehension只是Monad Comprehension的special case.

最簡單的:

[(x,y) | x &<- [1,3,5], y &<- [2,4,6]] -- or do { x &<- [1,3,5] , y &<- [2,4,6] , return (x,y) } -- &> [(1,2),(1,4),(1,6),(3,2),(3,4),(3,6),(5,2),(5,4),(5,6)]

把x, y的可能性都列出來, 組合在一起, 其實就是個笛卡爾{1,3,5} X {2,4,6}

這種列舉可能性的寫法用來做約束編程(Constraint Programming)就特別風騷,

來個簡單的題目(via Easy exhaustive search with the list monad : haskell)

-- S E N D -- + M O R E -- ----------- -- M O N E Y -- solution:

do let f = foldl1 (a -&> (a * 10 +)) [s,e,n,d,m,o,r,y,_,_] &<- permutations [0..9] let send = f [s,e,n,d] more = f [m,o,r,e] money = f [m,o,n,e,y] guard (s /= 0 m /= 0 send + more == money) return (send, more, money)

正如在我們通常的語言裡面數組也很重要一樣，每個範式都有自己的基本的數據結構。

但，FP中的list用法這個表格沒提啊。迭代用car then cdr，head then tail，都是 O(1)。拼接用(cons x ()) ,x:[]也是O(1)。

因為它的結構，從數學的角度上看，是非常美的。它的定義是recursive的。

舉個栗子，一個list of numbers的定義是either empty, or a pair which its head is a number, and its tail is a list of numbers. 而functional programming很多時候就是用這個數據結構recursive的特性來巧妙地解決各種問題的。

一個list，數組、鏈表、樹、圖全都有了，夫復何求？

因為list和遞歸是最簡單清晰的結構。stl裡面用iterator作為介面，也是操作list或者可以線性化的樹結構。