15

我有一个长而懒惰的序列，我想减少和懒惰地测试。一旦两个顺序元素=（或其他谓词）彼此不存在，我就想停止使用该列表，因为该列表的生成成本很高。是的，这听起来像take-while，但请进一步阅读。

我想写一些像这样简单而优雅的东西（假装一分钟every?像这样reduce）：

(every? = (range 100000000))

但这并不懒惰，因此它挂在无限序列上。我发现这几乎可以按我的意愿工作：

(apply = (range 100000000))

但是，我注意到序列分块会导致创建和测试额外的、不必要的元素。至少，我认为这就是以下代码中发生的情况：

;; Displays chunking behavior in groups of four on my system and prints 1 2 3 4
(apply = (map #(do (println %) %) (iterate inc 1)))

;; This prints 0 to 31
(apply = (map #(do (println %) %) (range)))

我找到了一种解决方法，使用take-while, 并count检查所用元素的数量，但这相当麻烦。

我应该礼貌地向 Rich Hickey 建议他正确地进行一些组合reduce和every?短路，还是我错过了一些已经存在的明显方式？

编辑：两个好心人发布了避免在惰性序列上分块的解决方案，但是在执行 时如何避免分块apply，这似乎在四个一组的分块中消耗？

编辑#2：正如 Stuart Sierra 所指出的，我独立发现，这实际上并不是分块。只是申请正常行事，所以我会称之为关闭并给他答案。对于那些感兴趣的人，我在单独的答案中包含了一个小函数来解决问题的减少部分。

4

3 回答 3

22

更正两次：一种更简单的方法来取消分块惰性序列：

(defn unchunk [s]
  (when (seq s)
    (lazy-seq
      (cons (first s)
            (unchunk (next s))))))

第一个版本被省略(when ...，所以它在输入序列结束后返回一个无限的 nil 序列。

使用第二个版本first而不是seq所以它停止在零。

RE：你的另一个问题，“我如何在申请时避免分块，这似乎在四个人的分块组中消耗”：

这是由于 的定义=，当给定一系列参数时，它强制前 4 个：

(defn =
  ;; ... other arities ...
  ([x y & more]
   (if (= x y)
     (if (next more)
       (recur y (first more) (next more))
       (= y (first more)))
     false)))
于 2010-08-04T20:30:11.837 回答
2

在 clojure.core 中查看 apply 的定义，可以清楚地了解为什么当apply与无限序列一起使用时它会以四个为一组进行分块。Reduce也不会短路……所以我只好写自己的解决方案：

(defn reducep
  "Like reduce, but for use with a predicate. Short-circuits on first false."
  ([p coll]
     (if-let [s (seq coll)]
       (reducep p (first s) (next s))
       (p)))
  ([p val coll]
     (if-let [s (seq coll)]
       (if-let [v (p val (first s))]
         (recur p (first s) (next s))
         false)
       true)))

然后使用 Stuart's unchunk (with a extra and)

(defn unchunk [s]
  (lazy-seq
   (cons (first s)
         (and (next s)
              (unchunk (next s))))))

我得到：

(reducep = (map #(do (print %) %) (unchunk (range)))) ;; Prints 01, returns false
(reducep = (map #(do (print %) %) (repeat 20 1))) ;; returns true
(reducep = (map #(do (print %) %) (unchunk [0 0 2 4 5]))) ;; Returns false
(reducep = (map #(do (print %) %) (unchunk [2 2 2 2 2]))) ;; returns true

如果这也适用于您，请修改它。

编辑：Stuart 修改后的 unchunk 版本可能比之前这篇文章中的版本更可取。

于 2010-08-05T12:16:53.230 回答
2

我在遇到 4clojure 问题的时间限制时发现了这篇文章，我找到了另一种避免 32 块的方法：

;; add another dummy sequence parameter to the map:
(apply = (map #(do (prn %2) %) (range) (range)))

map 的更高数量形式似乎不使用分块序列（clojure 1.5）

您必须对第二个参数做一些事情，因此明确这一点可能会更好：

(apply = (map (fn [i _] (prn i) i) (range) (range)))

这不像其他解决方案那样简洁，但可能有利于快速和肮脏的使用，例如测试“这是否因为分块而变慢？”。

关于apply，您可以使用partition从序列中获取对和 = 他们：

(every? #(apply = %) (partition 2 1
    (map (fn [i _] (prn i) i) (range) (range))))

虽然reducep看起来也很有用。

PS。我不想给人一种分块序列较慢的印象，事实并非如此。我的问题是 4clojure 测试用例在我的 seq 生成函数上在一系列值上调用“第一个”，所以分块意味着我做了 32 倍的工作。（PPS。我的代码还是太慢了）

于 2013-05-15T13:59:11.920 回答