Welcome! Please see the About page for a little more info on how this works.

0 votes
in Collections by

reduce-kv works as expected on vectors with the element index passed as the "key" argument. However, it fails with a subvec because clojure.lang.APersistentVector$SubVector does not implement IKVReduce.

(reduce-kv + 0 (link: 1 2 3))
9

(reduce-kv + 0 (subvec (link: 1 2 3) 1))
IllegalArgumentException No implementation of method: :kv-reduce of protocol: #'clojure.core.protocols/IKVReduce found for class: clojure.lang.APersistentVector$SubVector clojure.core/-cache-protocol-fn (core_deftype.clj:583)

One work around is to copy the subvec into a vector:

(reduce-kv + 0 (into (link: ) (subvec (link: 1 2 3) 1)))
6

Note however, the vec would not work here. Since Clojure 1.7, vec will return a subvec rather than copying.

(reduce-kv + 0 (vec (subvec (link: 1 2 3) 1)))
IllegalArgumentException No implementation of method: :kv-reduce of protocol: #'clojure.core.protocols/IKVReduce found for class: clojure.lang.APersistentVector$SubVector clojure.core/-cache-protocol-fn (core_deftype.clj:583)

The Clojure user expects that a subvector supports all of the normal vector operations and this exception is confusing. The cause of the problem is that subvec returns a clojure.lang.APersistentVector$SubVector which does not implement clojure.lang.IKVReduce. PersistentVector inherits from APersistentVector and implements IKVReduce but SubVector doesn't get any IKVReduce support. This was probably just an oversight.

There are two patches attached. The first fixed the problem by extending the IKVReduce protocol in core.clj. That's convenient for Clojure users to drop into their code as a work-around. The second patch, as suggested by Alex Miller, adds the Java implementation of the IKVReduce interface directly to APersistentVector$SubVector. The second patch is the one that should be reviewed. The same test is included in both patches.

9 Answers

0 votes
by

Comment made by: steveminer@gmail.com

Here is my current work-around:

`
(extend-type clojure.lang.APersistentVector$SubVector
clojure.core.protocols/IKVReduce
(kv-reduce [subv f init]

(transduce (map-indexed vector)
           (fn ([ret] ret) ([ret [k v]] (f ret k v)))
           init
           subv)))

`

In my tests it was usually faster to copy the subvec into a regular vector but I like the look of the transduce fix. It would probably be faster to add a native Java implementation in APersistentVector.java. I'm willing to do the work if the Clojure/core team wants a patch.

0 votes
by
_Comment made by: steveminer@gmail.com_

Revised work-around using more interop for better performance.  Comparable to the speed of normal vector reduce-kv.


(when-not (satisfies?   clojure.core.protocols/IKVReduce (subvec [1] 0))
  (extend-type clojure.lang.APersistentVector$SubVector
    clojure.core.protocols/IKVReduce
    (kv-reduce
      [subv f init]
      (let [cnt (.count subv)]
        (loop [k 0 ret init]
          (if (< k cnt)
            (let [val (.nth subv k)
                  ret (f ret k val)]
              (if (reduced? ret)
                @ret
                (recur (inc k) ret)))
            ret))))))
0 votes
by

Comment made by: steveminer@gmail.com

support IKVReduce for SubVector

0 votes
by

Comment made by: steveminer@gmail.com

Patch also adds test for reduce-kv on regular vector and subvector.

0 votes
by

Comment made by: alexmiller

Why not implement IKVReduce directly in APersistentVector$SubVector?

0 votes
by

Comment made by: steveminer@gmail.com

Java implementation of IKVReduce on SubVector

0 votes
by

Comment made by: steveminer@gmail.com

Yes, that makes sense. I hesitated because I didn't want to rework the hierarchy to make SubVector a subclass of PersistentVector but that wasn't necessary to fix the bug. CLJ-2065-Support-IKVReduce-on-SubVector.patch is just the Java side, plus the same test.

0 votes
by

Comment made by: steveminer@gmail.com

Updated patch to inline nth() call, avoiding unnecessary bounds checking.

0 votes
by
Reference: https://clojure.atlassian.net/browse/CLJ-2065 (reported by steveminer@gmail.com)
...