How to use Java array of primitive types as key of Clojure map?

[John Fingerhut]

If you don't do anything special, and create several Java array of bytes (for example) and use them as keys in a Clojure map, the default hashCode and equals implementation will cause two arrays with identical contents to be treated as different keys in the map, unless they are also == in Java.

I'd like to use Java byte arrays as keys in Clojure maps, but haven't been able to figure out how yet.  I know that java.util.Arrays/hashCode and java.util.Arrays/equals have the behavior I want, so one way would be to get Clojure to somehow use those methods when given the byte arrays as keys.  That led me to think of trying deftype to make my own type Key with the desired implementation of hashCode and equals.  I'm using Clojure 1.2, and I don't see how to give the appropriate type hints to declare that something is a Java byte array.  Here is one attempt for Java int arrays instead of Java byte arrays:

(definterface IKey
  (^ints key [])
  (equals [other-key] "Compare two Keys for value equality, i.e. same length and same bytes in array value")
  (hashCode [] "Return a hash code that is the same for equal keys, and usually different for different keys"))


(deftype Key [^ints key]
  IKey
  (key [this] key)
  (equals [this other-key]
    (let [^Key other other-key]
      (java.util.Arrays/equals key (.key other))))
  (hashCode [this]
    (java.util.Arrays/hashCode key))

  Object
  (toString [this]
    (apply str (map char key))))

When I try to evaluate the deftype statement, I get an error like this:

java.lang.NoClassDefFoundError: java/lang/ints

Same error if I replace ^ints with #^ints.  If I leave out the type hints for the field key completely, I get the following error when trying to evaluate the deftype:

java.lang.VerifyError: (class: user/Key, method: hashCode signature: ()Ljava/lang/Object;) Expecting to find object/array on stack

I'm not wedded to deftype as being part of the solution.  My real goal is as high performance way of using Java byte/int/some-native-type arrays as map keys, i.e. with no reflection warnings.

Thanks,
Andy

[Nicolas Oury]

Multiple things:

the internal type name for int arrays is [I

So you should try something like:
(deftype T [^"[I" keys ]

....)

then you are looking to overload equals and hashCode from the Object interface
(deftype T [^"[I" keys ]
Object
(equals [x other]
(java.util.Arrays/equals key (.key other)))

....)

And replace other by ^T other, to prevent reflection.
(You should actually check that it is of the right type, by using
(identical? (type other) T). (instance? does not seem to work in its
own deftype) )

Best,

Nicolas.

[Stuart Halloway]

Be super-careful doing this. Java's array equality and hashCode are correct: since arrays are mutable, they are not values. So equals and hashCode are correctly identity-based.

Also, 1.2's vector-of lets you have vectors of primitives, which may give you the perf you need.

But, if you can ensure that the arrays will be used as values:

(ns key

  (:require [clojure.string :as str]))

(deftype Key [key]

  Object

  (equals [this other]

          (if (= (class this) (class other))

            (java.util.Arrays/equals ^ints key ^ints (.key ^Key other))

            false))

  (hashCode [this]

    (java.util.Arrays/hashCode ^ints key))

  (toString [this]

            (str/join \, (seq key))))

(defn int-key [coll]

  (Key. (int-array (count coll) coll)))

Stu

Stuart Halloway

Clojure/core

http://clojure.com

--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient with your first post.
To unsubscribe from this group, send email to
clojure+u...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en

[John Fingerhut]

Thanks!  That worked for me.  Understood on the precautions about these things not being immutable, and thus potentially unsafe as hash keys (and anything else that expects immutability, whether that is obvious or not).

This raises the question in my mind -- will there be something in Clojure, perhaps for Clojure-in-Clojure, that allows any old Clojure programmer to create their own immutable types?  Perhaps with deftype or some future extension of it?  Sorry if this is widely known and I'm just behind the news, but I had read recently that a motivation for deftype is to get closer to the point where more of Clojure can be implemented in itself.

I don't expect there to be *guarantees* provided by the compiler or run-time that the interface provided above a given API layer implements a persistent data structure, because that sounds impossible to guarantee in general.  But the only guarantee that we have that Clojure vectors, maps, sequences, etc. are immutable and persistent is that the Java implementations correctly implement those features, with no automated checking of those properties.

Thanks,

Andy