CODEWITHSUNDEEP
recursionclojurefunctional-programmingreducefold
hawkeye
hawkeye

Reputation: 35702

How can operations like map, filter and reverse can be defined in terms of a reduce?

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?

Upvotes: 2

Views: 591

Answers (3)

noisesmith
noisesmith

Reputation: 20194

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)

Upvotes: 3

Thumbnail
Thumbnail

Reputation: 13473

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.

Upvotes: 5

Don Stewart
Don Stewart

Reputation: 137957

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.

Upvotes: 5

Related Questions