match? mismatches predicates when applied to keys in maps

[dchelimsky]

> (require '[matcher-combinators.standalone :refer [match?]])
nil
> (match? {:a :b} {:a :b})
true
> (match? keyword? (first (keys {:a :b})))
true
> (match? keyword? (first (vals {:a :b})))
true
> (match? {:a keyword?} {:a :b})
true
> (match? {keyword? :b} {:a :b})
false

[dchelimsky]

/cc @philomates @nubank/eng-prod-test

[philomates]

This will probably slow matching down quite a bit because matching keys in a map instead of normal clojure equality is complexity-wise like matching an unordered list. Matching an unordered list is slow because you can have "overlapping" predicates (odd? is a superset of #(= 1)), where you basically need to exhaust all orderings before you are sure the thing doesn't match.

I sorta think we shouldn't implement this, given the runtime cost, additional implementation complexity, and as far as I know, nobody has felt its absence yet. Or we could implement it as a special matcher, such that key matching only happens when the expected map is wrapped in a holistic-embeds matcher or something (name is joke, but you get the point hopefully)

[philomates]

Implementation-wise though, I had the idea that matching something like

(match?
  {keyword? odd? :x pos?}
  {:a 1 :x -1 :whatever "foo"}

could be recast as

(match?
  (embeds [[keyword? odd?] [:x pos?]])
  [[:a 1] [:x -1] [:whatever "foo"]])

with some adaptations on the resulting mismatch message

[dchelimsky]

@philomates if we don't add support for predicates, we should at least document that fact. Maybe even an error or warning? WDYT?

[philomates]

since

(match? {symbol? 2
         symbol? 1}
        {'x 1 'y 2})

fails with

Syntax error reading source at (REPL:207:20).
Duplicate key: symbol?

we could do something similar to what we did with set-equals and set-embeds that allowed for writing a matcher that effectively works as #{odd? odd?}.
@mk had the suggestion that the embeds and equals matchers could add a 2-arity implementation that allows specifying the type that a thing should be matched as. So set-equals could then be (partial embeds 'set) and we could do map key matching with

(match? (m/embeds 'map
                  [[symbol? 2]
                   [symbol? 1]])
        {'x 1 'y 2})

I'm not sure if adding this functionality is worth the additional complexity in both the library's capabilities, speed, and its implementation.