Как можно определить такие операции, как map, filter и reverse, в терминах редукции?

Это верно, если мы не заботимся о лени. В Clojure map и filter ленивы, а сокращение нетерпеливо. Мало того, что reverse не ленивый, стандартное определение использует сокращение. По модулю лени мы можем получить эквивалентные результаты для остальных:

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)

Как можно определить такие операции, как map, filter и reverse, в терминах редукции?

Это известно как "универсальность сгиба". 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) []

or 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. Учебное пособие по универсальности и выразительности сгибов, Грэм Хаттон, 1999.
2. Запись foldl с помощью foldr, здесь.

Отредактировано для распознавания 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.