如何在Clojure中使用reduce实现map功能

Question

在书籍Clojure for the Brave and True中，在涵盖reduce的章节末尾，有一个挑战：

如果你想要一个真正让你大开眼界的练习，请尝试使用reduce实现map

结果证明这比我想象的要难得多（至少对于我这个Clojure初学者来说）。经过很多小时的努力，我想出了这个：

(defn map-as-reduce
  [f coll]
  (reduce #(cons (f %2) %1) '() (reverse coll)))

有更好的方法吗？我特别不满意的是，为了使它正常工作，我必须翻转输入的集合。这似乎有点不优雅！

- mluisbrown

Answer 1

记住，在向量的末尾进行高效插入：

(defn map' [f coll]
  (reduce #(conj %1 (f %2)) [] coll))

示例：

(map' inc [1 2 3])
;=> [2 3 4]

这个map'和原始的map之间的一个区别是，原始的map返回一个ISeq而不仅仅是Seqable：

(seq? (map inc [1 2 3]))
;=> true

(seq? (map' inc [1 2 3]))
;=> false

你可以通过将上述的 map' 实现与 seq 进行组合来解决这个问题：

(defn map' [f coll]
  (seq (reduce #(conj %1 (f %2)) [] coll)))

现在最重要的区别是，虽然原始的 map 是惰性的，但这个 map' 是及早求值的，因为 reduce 是及早求值的。

- Sam Estep

Answer 2

只是为了好玩： map函数确实可以接受一个以上的集合作为参数。以下是一种扩展实现：

(defn map-with-reduce
  ([f coll] (seq (reduce #(conj %1 (f %2)) [] coll)))
  ([f coll & colls]
    (let [colls (cons coll colls)]
      (map-with-reduce (partial apply f)
                       (partition (count colls) 
                                  (apply interleave colls))))))

在 REPL 中：

user> (map-with-reduce inc [1 2 3])
(2 3 4)

user> (map-with-reduce + [1 2 3] [4 5] [6 7 8])
(11 14)

- leetwinski

Answer 3

真正的地图在其集合参数上调用seq并返回一个惰性seq，所以也许这样做可以让它更接近真正的地图？

(defn my-map
  [f coll]
  (lazy-seq (reduce #(conj %1 (f %2)) [] (seq coll))))

我本想将此作为评论添加，但我没有足够的声望。:)

- Enrique Montalvo

Answer 4

通常更常见的是反转结果，而不是输入。在递归处理单向链表时，这是一种常见的习惯用法。它保留了这种数据结构的线性复杂度。

您可能希望为其他seq提供不同的实现，例如基于conj而不是cons的向量。

我不会过于担心在这种练习中的优雅。

- Svante

---

我不明白为什么反转结果而不是输入会有所不同；无论哪种方式，复杂度都是线性的。 - Sam Estep

@SamEstep：是的，好的。但通常更常见的是反转结果。 - Svante

我并不是很理解你关于“为其他seq提供其他实现”的评论；此页面上所有map的实现都适用于所有Seqable输入。如果你的意思是生成不同类型的序列作为结果，那么我认为这样做没有太大的意义（除了可能会提高性能），因为人们可以轻松地将map与vec或其他东西组合起来。 - Sam Estep

@SamEstep：性能正是我的重点。您不需要反转向量。 - Svante

Answer 5

您可以使用 conj 将内容追加到向量中，而不是将其添加到列表的开头：

(defn my-map [f coll]
  (reduce (fn [result item]
              (conj result (f item)))
          [] coll))

(my-map inc [1 2 3]) => [2 3 4] 

- Adam Lee

Answer 6

如前所述，您不必反转输入。cons将项目添加到序列的开头（即使在向量中），而conj始终以最自然的方式添加，它总是以集合的最快方式添加项目。对于列表，它会从左到右添加，对于向量，也是从左到右添加。

我注意到大多数建议使用'reduce'，因此让我建议主要使用递归的这个方案：

(defn my-map [f coll]
 (loop [f f coll coll acc []]
   (if (empty? coll)
     acc
     (recur f (rest coll) (conj acc (f (first coll)))))))

- Lewix

---

这个问题特别提到了使用reduce，因此，虽然有趣，但这个答案并没有回答这个问题。 - mluisbrown

@mluisbrown 是的，你说得对。我可能错过了它明确说明要使用“reduce”的部分。 - Lewix