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

Question

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?

Answer 1

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.