如何通过减少来定义地图,过滤器和反向等操作？

Question

在这篇博客文章"JavaScript中的CSP和传感器"中,作者指出:

首先,我们必须认识到许多数组(或其他集合)操作map,filter并且reverse可以用a来定义reduce.

我的问题是:如何通过减少来定义地图,过滤器和反向等操作？你能在Clojure中提供一些例子吗？

Answer 1

编辑承认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))))

如果我们在向量中积累,我们可以没有reverses和vecs:

(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 2

如何通过减少来定义地图,过滤器和反向等操作？

这被称为"折叠的普遍性".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. 关于折叠的普遍性和表现力的教程,Graham Hutton,1999.
2. 在这里使用foldr编写foldl.