为什么partition-by会多次遍历元素？

Question

我发现当发生拆分时，partition-by中的f对同一元素调用两次。

(partition-by
 #(do (println %)
   (rand))
 [1 2 3])

1
2
2
3
3
((1) (2) (3))

看看每次我们如何拆分，所以元素2和3会打印两次。

这是不是bug？它应该是这样做吗？

我注意到，因为我有一个需要统计元素出现的次数以便在适当时候拆分的场景，这破坏了我的计数。

编辑：看起来transducer版本没有这种行为

(into []
 (partition-by
  #(do (println %)
    (rand)))
 [1 2 3])

1
2
3
[[1] [2] [3]]

Answer 1

([f coll]
 (lazy-seq
  (when-let [s (seq coll)]
    (let [fst (first s)
          fv (f fst)
          run (cons fst (take-while #(= fv (f %)) (next s)))]
      (cons run (partition-by f (lazy-seq (drop (count run) s))))))))

看起来f在绑定fv时被调用了一次。由于take-while部分没有生成任何类似键，所以run的值是'(1)。然而，f "是"在s的其余部分的第一值上被调用的，所以2被打印了一次。当partition-by在lazy-seq构建过程中进行伪递归时，新分区的第一个参数现在是2。fv是通过在2上调用f来确定的，这打印两个，依此类推。过程重复。

传感器变体永远不会递归地通过下一个分区的头部，因此它仅对原始输入的每个元素调用一次f。

注意：我们可以这样推导出一个无状态的1次分片函数变体

user> (defn partition-by-once [f coll]
        (->> coll
             (map (fn [x] [(f x) x]))
             (partition-by first)
             (map #(map second %))))
#'user/partition-by-once
user> (partition-by-once #(do (println %)
                               (rand)) [1 2 3])
1
2
3
((1) (2) (3))

我们还可以使用传感器使用的 volatile 技巧来实现

    (defn partition-by-once-statefully
      [f coll]
      (let [pv   (volatile! ::none)
            test (fn [v] (vreset! pv (f v)))
            aux  (fn aux
                   ([coll]
                    (lazy-seq
                     (when-let [s (seq coll)]
                       (let [fst (first coll)
                             fv  @pv
                             run (cons fst (take-while #(= fv (test %)) (next s)))]
                         (cons run (aux (lazy-seq (drop (count run) s))))))))
                  ([fst remaining]
                   (if-let [s (seq remaining)]
                     (let [fv  (test fst)
                           run (cons fst (take-while #(= fv (test %)) s))]
                       (cons run (aux (lazy-seq (drop (dec (count run)) s)))))
                     `((~fst)))))]
        (when-let [s (seq coll)]
          (aux  (first coll) (next coll)))))

    user> (doall (partition-by-once-vol (fn [v] (println v) (odd? v)) [1 2 3 5 7 8 10 11]))
    1
    2
    3
    5
    7
    8
    10
    11
    ((1) (2) (3 5 7) (8 10) (11))