In this blog entry, "CSP and transducers in JavaScript", the author states:
First, we have to realise that many array (or other collection) operations like
map,filterandreversecan be defined in terms of areduce.
My question is: How can operations like map, filter and reverse can be defined in terms of a reduce? Could you provide examples in Clojure?
How can operations like map, filter and reverse can be defined in terms of a reduce?
This is known as the "universality of fold". fold below is the natural fold (foldr):
Obviously, various reductions can be described via fold:
sum :: [Int] -> Int product :: [Int] -> Int
sum = fold (+) 0 product = fold (*) 1
and :: [Bool] -> Bool or :: [Bool] -> Bool
and = fold (&&) True or = fold (||) False
But we can also write non-obvious reductions:
-- appending a list
(++) :: [a] -> [a] -> [a]
(++ ys) = fold (:) ys
-- reversing a list
reverse :: [a] -> [a]
reverse = fold (\x xs -> xs ++[x]) []
and map in general:
map :: (a -> b) -> ([a] -> [b])
map f = fold (\x xs -> f x : xs) []
or filter:
filter :: (a -> Bool) -> ([a] -> [a])
filter p = fold (\x xs -> if p x then x : xs else xs) []
or even fold left:
foldl f v xs = fold (\x g -> (\a -> g (f a x))) id xs v
References:
Edited to recognize mapv and filterv.
The standard reverse is defined in terms of reduce:
(defn reverse [coll]
(reduce conj () coll))
map and filter are lazy, so can operate on infinite sequences. There is no way to do this with reduce.
That being said, reduce can implement mapv and filterv, the eager analogues of map and 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))))
We can do without the reverses and the vecs if we accumulate in vectors:
(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))
This last is almost how the standard filterv is implemented.
conj for reverse but cons (and outer reverse) for map/filter?reverse, (defn conj [coll x] ...) has the arguments in the correct order for reduce; cons would need to be wrapped in a function reversing its arguments: #(cons %2 %1). In map, the cons inside reduce stacks up - hence reverses - the results, so they need to be reversed again. The same applies to filter. The Clojure idiom is to use a vector in such cases - avoiding the need to reverse the product. I've appended versions that do this. Note that these are returned as sequences, in case someone uses conj or disj on them.This is true, if we don't care about laziness. In Clojure, map and filter are lazy, but reduce is eager. Not only is reverse not lazy, but the standard definition uses reduce. Modulo the laziness, we can get equivalent results for the others:
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)
concat, in reduce you pick your own base case, so pick the one that has theconjbehavior needed.