2

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, filter and reverse can be defined in terms of a reduce.

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?

Don Stewart
  • 137,316
  • 36
  • 365
  • 468
hawkeye
  • 34,745
  • 30
  • 150
  • 304
  • 1
    This is an odd place to use `concat`, in reduce you pick your own base case, so pick the one that has the `conj` behavior needed. – noisesmith Sep 03 '14 at 23:03

3 Answers3

5

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.

Thumbnail
  • 13,293
  • 2
  • 29
  • 37
  • Why the `conj` for reverse but `cons` (and outer reverse) for map/filter? – user2864740 Sep 03 '14 at 23:10
  • @user2864740 In `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. – Thumbnail Sep 03 '14 at 23:32
  • @user2864740 the last edit invalidated some of my reply. – Thumbnail Sep 04 '14 at 17:38
5

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:

  1. A tutorial on the universality and expressiveness of fold, Graham Hutton, 1999.
  2. Writing foldl using foldr, here.
Community
  • 1
  • 1
Don Stewart
  • 137,316
  • 36
  • 365
  • 468
  • it's an honour to have you answer my question. Its great all the work the Haskell guys are doing to reach out to the Clojure community. I'm working through RWH at the moment - up to Ch 7. – hawkeye Sep 04 '14 at 10:29
  • 1
    @hawkeye What work, hawkeye? I'm intrigued. Is Clojure Haskell's bulldog, as Huxley was Darwin's bulldog. – Thumbnail Sep 04 '14 at 17:46
  • @Thumbnail "..undecided about purely function code, but despite this he was wholehearted in his public support of functional programming.." - seems like the analogy could work ;-) – user2864740 Sep 04 '14 at 20:19
3

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)
noisesmith
  • 20,076
  • 2
  • 41
  • 49