recursion - 如何根据 reduce 定义 map、filter 和 reverse 等操作？

Question

在此博客条目中，"CSP and transducers in JavaScript" ，作者指出:

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.

我的问题是:如何根据 reduce 定义 map、filter 和 reverse 等操作？您能提供 Clojure 中的示例吗？

Answer 1

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

这被称为 "universality of fold" . 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) []

或过滤器:

filter :: (a -> Bool) -> ([a] -> [a])
filter p = fold (\x xs -> if p x then x : xs else xs) []

甚至向左折叠:

foldl f v xs = fold (\x g -> (\a -> g (f a x))) id xs v

---

引用资料:

1. A tutorial on the universality and expressiveness of fold ，格雷厄姆·赫顿，1999 年。
2. Writing foldl using foldr ，在这里。