如何定義映射，過濾器和反轉等操作？

Question

在此博客條目，"CSP and transducers in JavaScript"，筆者指出：

首先，我們必須認識到，許多陣列（或其他集合），如map，filter和reverse操作可以在一個reduce來定義。

我的問題是：如何能像地圖，過濾器和相反的操作可以在一個減少來定義？你能提供Clojure的例子嗎？

Answer 1

這是真的，如果我們不關心懶惰。在Clojure中，map和filter是懶惰的，但減少是渴望的。 reverse不僅懶惰，而且標準定義使用reduce。模的懶惰，我們可以得到同樣的結果換了別人：

user> (defn eager-map [f coll] 
     (reduce (fn [acc v] (conj acc (f v))) 
     [] 
     coll)) 
#'user/eager-map 
user> (eager-map inc (range 10)) 
[1 2 3 4 5 6 7 8 9 10] 

user> (defn eager-filter [f coll] 
     (reduce (fn [acc v] (if (f v) (conj acc v) acc)) 
       [] 
       coll)) 
#'user/eager-filter 
user> (eager-filter even? (range 10)) 
[0 2 4 6 8] 

user> (defn eager-reverse [coll] 
     (reduce conj() coll)) 
#'user/eager-reverse 
user> (eager-reverse (range 10)) 
(9 8 7 6 5 4 3 2 1 0) 

Answer 2

編輯承認mapv和filterv。

---

標準reverse在的reduce來定義：

(defn reverse [coll] 
    (reduce conj() coll)) 

map和filter懶惰，所以可以在無限的順序進行操作。沒有辦法與reduce做到這一點。

話雖這麼說，reduce可以實現mapv和filterv的map和filter渴望的類似物。

(defn mapv [f coll] 
    (vec (reverse (reduce (fn [acc x] (cons (f x) acc))() coll)))) 

(defn filterv [pred coll] 
    (vec (reverse (reduce (fn [acc x] (if (pred x) (cons x acc) acc))() coll)))) 

---

如果我們在矢量積累，我們可以不reverse S和vec就做：

(defn mapv [f coll] 
    (reduce (fn [acc x] (conj acc (f x))) [] coll)) 

(defn filterv [pred coll] 
    (reduce (fn [acc x] (if (pred x) (conj acc x) acc)) [] coll)) 

最後這幾乎是怎樣的標準filterv實現。

Answer 3

如何定義映射，過濾器和反轉等操作可以通過reduce來定義？

這就是所謂的"universality of fold"。下面fold是天然倍（foldr相似）：

顯然，各種減少可以通過摺疊來描述：

sum :: [Int] -> Int   product :: [Int] -> Int 
sum = fold (+) 0    product = fold (*) 1 

and :: [Bool] -> Bool   or :: [Bool] -> Bool 
and = fold (&&) True   or = fold (||) False 

但是，我們也可以寫非顯而易見的減少：

-- appending a list 
(++) :: [a] -> [a] -> [a] 
(++ ys) = fold (:) ys 

-- reversing a list 
reverse :: [a] -> [a] 
reverse = fold (\x xs -> xs ++[x]) [] 

和map一般情況下：

map :: (a -> b) -> ([a] -> [b]) 
map f = fold (\x xs -> f x : xs) [] 

或filter：

filter :: (a -> Bool) -> ([a] -> [a]) 
filter p = fold (\x xs -> if p x then x : xs else xs) [] 

甚至fold left：

foldl f v xs = fold (\x g -> (\a -> g (f a x))) id xs v 

---

參考文獻：

1. A tutorial on the universality and expressiveness of fold，格雷厄姆赫頓，1999
2. Writing foldl using foldr，在這裏。