Как можно определить такие операции, как map, filter и reverse, с точки зрения сокращения?

Question

В этой записи блога "CSP и преобразователи в JavaScript" автор заявляет:

Во-первых, мы должны понимать, что многие операции с массивами (или другими коллекциями), такие как map, filter а также reverse можно определить с точки зрения reduce,

Мой вопрос: как можно определить такие операции, как отображение, фильтрация и обратное отображение, в терминах уменьшения? Не могли бы вы привести примеры в Clojure?

Answer 1

Это правда, если мы не заботимся о лени. В 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)

Answer 2

Отредактировано, чтобы признать 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))))

---

Мы можем обойтись без reverse с и vec s, если мы накапливаем в векторах:

(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 реализовано.

Answer 3

Как можно определить такие операции, как map, filter и reverse, с точки зрения сокращения?

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

Но мы также можем написать неочевидные сокращения:

-- 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) []

или же 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, здесь.