Clojure: Remove item from sorted-set-by

Question

How can I remove an element from a sorted-set-by? My problem is as follows:

;; Set works fine
(-> #{:a :b :c :d}
    (disj :c))
=> #{:b :d :a}

;; Sorted set works fine
(-> (sorted-set :a :b :c :d)
    (disj :c))
 => #{:a :b :d}

;; Set sorted by custom function does not work
(let [values {:a {:x 1}
              :b {:x 0.4}
              :c {:x 9}
              :d {:x 5}}
      x-val (fn [a b]
              (if (> (get-in values [a :x]) (get-in values [b :x]))
                1
                -1))]
  (-> (sorted-set-by x-val :a :b :c :d) 
      (disj :c)))
  => #{:b :a :d :c} ;; should be #{:b :a :d}

Results won't change if I modify the x-val function to

x-val (fn [a b]
        (cond 
          (identical? a b) 0
          (> (get-in values [a :x]) (get-in values [b :x])) 1
          :else -1))]

• Why does this not work?
• How can I make this work?

Bonus question I want to try a heavily modified version of this to speed up a working A* implementation. Are there better datastructures to keep a set sorted by a map item?

Answer 1

You were already there

(let [values {:a {:x 1}
              :b {:x 0.4}
              :c {:x 9}
              :d {:x 5}}
      x-val (fn [a b]
              (let [{x :x} (values a)
                    {y :x} (values b)]
                (if (not= a b) 
                  (compare x y)
                  0)))] 
  (-> (sorted-set-by x-val :a :b :c :d) 
      (disj :c)))

The key being that equality (returning a comparson value of 0) is needed to support removal. Even

(let [values {:a {:x 1}
              :b {:x 0.4}
              :c {:x 9}
              :d {:x 5}}
      x-val (fn [a b]
              (let [{x :x} (values a)
                    {y :x} (values b)]
                  (compare x y)))]
  (-> (sorted-set-by x-val :a :b :c :d) 
      (disj :c)))

will work. Your version with identical? works in my REPL (on Arch Linux) - so there must be something else going on. If you try

(let [values {:a {:x 1}
              :b {:x 0.4}
              :c {:x 9}
              :d {:x 5}}
      x-val (fn [a b]
              (cond 
                (identical? a b) 0
                  (> (get-in values [a :x]) (get-in values [b :x])) 1
                    :else -1))]
  (-> (sorted-set-by x-val :a :b :c :d) 
      (disj :c)))

on Try Clojure you can see for yourself. Of course your initial version could be modified as follows

(let [values {:a {:x 1}
              :b {:x 0.4}
              :c {:x 9}
              :d {:x 5}}
      x-val (fn [a b]
              (if (= a b)
                0
                (if (> (get-in values [a :x]) (get-in values [b :x])) 1 -1)))]
  (-> (sorted-set-by x-val :a :b :c :d) 
      (disj :c)))

Addendum: How does Clojure get (potentially) three states out of a two argument predicate?

A brief REPL session should illustrate what Clojure does to use predicates as comparators:

user=> (> 1 2)
false
user=> (> 2 1)
true
user=> (> 1 1)
false
user=> (def cmp-from-gt (comparator >))
#'user/cmp-from-gt
user=> (cmp-from-gt 1 2)
1
user=> (cmp-from-gt 2 1)
-1
user=> (cmp-from-gt 1 1)
0
user=> (defn pfn->cfn 
  #_=>   [pfn]
  #_=>   (fn [a b] 
  #_=>     (if (pfn a b) -1 (if (pfn b a) 1 0))))
#'user/pfn->cfn
user=> (def cfn-from-gt (pfn->cfn >))
#'user/cfn-from-gt
user=> (cfn-from-gt 1 2)
1
user=> (cfn-from-gt 2 1)
-1
user=> (cfn-from-gt 1 1)
0

Answer 2

The comparator function for sorted-set-by should return a boolean rather than an integer.

Replace

(fn [a b]
  (if (> (get-in values [a :x]) (get-in values [b :x]))
    1
    -1))

with

(fn [a b]
  (> (get-in values [a :x]) (get-in values [b :x])))

and it should work correctly.

EDIT: To clarify, you can use compare-style functions instead of boolean functions for the comparator, but in that case that function will also be used for equality tests on the set. If you don't want to specify equality explicitly and rather would like Clojure to use a default, use boolean.

If you do recognize the equality case and return 0 for it, as in your 2nd example, the disj does work as intended. It is not correct that the results won't change.