在 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) 的地图。

更有趣的修复方法是添加对键中变量的支持。这对我来说很有价值（并且很有趣）。这改变了算法，因为没有排序的集合使可能的统一数量倍增，例如（统一 {: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 呈报）