在 Clojure 1.6 和 Clojure 1.7 之间，地图统一的问题停止了正确工作

Question

在 1.9.0-alpha14 中


dev=> (clojure.core.unify/unify {:a '?x, :c :d} {:c :d, :a :b})
nil
dev=> (clojure.core.unify/unify {:a '?x, :c :d} {:a :b, :c :d})
{?x :b}

Answer 1

_评论者：eraserhd_

在 UNIFY-6 中有一个提示，我们预期它会工作，尽管当前的算法从未支持键中的变量。它确实统一了类似键的值，但它依赖于具有相同键集的两个地图具有相同的迭代顺序。这就是它出问题的原因。

一个简单的修复方法是恢复先前的行为 - 先前的行为是 O(n)（依赖于迭代地图键的顺序为 O(n)），简单的修复方法会使它类似于 O(n log_32 n) 对于地图。

一个更有趣的修复方法是添加对键中变量的支持。我认为这很有价值（并且有趣）。这改变了算法，因为集合的无序性使得可能的统一（unification）更多，例如（unify {:a 1, :b 2} {?x _, ?y _}) 有两个统一：{:x :a, :y :b} 和 {:x :b, :y :a}，因此回溯（或类似的方法）变得必要。

这个相同的机制可以用于集合，如 UNIFY-8 中所述。

是否应考虑“有趣的”修复，还是我应该只做“简单的”？

Answer 2

参考： https://clojure.atlassian.net/browse/UNIFY-9（eraserhd 报告）