爲什麼fold和reduce被認爲是根本性的 - 當然，所有的東西都是根據cons和car定義的？

Question

我們可以看到，我們可以使用reduce/foldl1作爲函數by which we can define other higher order functions such as map, filter and reverse。

(defn mapl [f coll] 
    (reduce (fn [r x] (conj r (f x))) 
      [] coll)) 

(defn filterl [pred coll] 
    (reduce (fn [r x] (if (pred x) (conj r x) r)) 
      [] coll)) 

(defn mapcatl [f coll] 
    (reduce (fn [r x] (reduce conj r (f x))) 
      [] coll)) 

我們也似乎能夠按照foldr的方式做到這一點。根據foldr from Rich Hickey's Transducers talk在17:25，這裏是map和filter。

(defn mapr [f coll] 
    (foldr (fn [x r] (cons (f x) r)) 
     () coll)) 

(defn filterr [pred coll] 
    (foldr (fn [x r] (if (pred x) (cons x r) r)) 
     () coll)) 

現在，我們可以定義map，foldl（reduce）和foldr在first，rest和cons（car，cdr和cons）方面：

(defn foldr [f z xs] 
    (if (null? xs) 
     z 
     (f (first xs) (foldr f z (rest xs))))) 

(defn foldl [f z xs] 
    (if (null? xs) 
     z 
     (foldl f (f z (first xs)) (rest xs)))) 

(defn map [f lst] 
    (if (null? lst) 
     '() 
     (cons (f (first lst)) (map f (rest lst))))) 

我的問題是爲什麼fold和reduce被認爲是根本性的 - 當然一切都按照cons,cdr和car？這是不是在看錯級別的東西？

Answer 1

我以爲Rich Hickey正是在他的talk about transducers中解釋過的。

他認爲folds是轉變的基本概念。它不需要知道它在做什麼結構以及如何操作這個結構。

您剛剛根據自身定義fold，cdr,car和rest。 Rich所爭辯的是，fold本身就是一個抽象的概念，與它所操作的數據結構分開，只要我們提供某些實際在數據結構上運行的函數，它就能按預期工作。

所以最終都是關於顧慮和可重用性的分離。

Answer 2

摺疊是一種統一的原則性數據處理框架，因爲它們對應于歸納數據定義。他們不是特設的。 cons/car/cdr是創建數據（和代碼）的基石，但是以無原則的方式（我們可以做任何事情，並且專門處理它）。摺疊更高層次，更有紀律，更可預測，更容易推理。

鑑於map，filter，mapcat爲列表的臨時實現，我們可以看到它們中有類似的東西 - 遵循數據結構的代碼結構（列表，由cons節點構成，列表對應於組合函數的兩個參數）。這是摺疊。

在那次演講中，Rich Hickey抽象出了階梯函數。但他並沒有對數據進行抽象。用於摺疊標記樹的任何組合函數都需要三個參數，而不是兩個。所以他的功能仍然是從概念上摺疊列表，只是它們對列表的具體實現進行了抽象 - 無論是作爲單元格，哈希陣列樹，不管。

Answer 3

大多數使用lispy語言的操作員都會有一個可以用來定義它的合作伙伴，反之亦然。這個屬性被稱爲「metacircularity」。沒有一個特定的基本操作符集合，這是允許該語言給出的全部可編程性的基本最小值。

你可以閱讀更多的文章： http://home.pipeline.com/~hbaker1/MetaCircular.html