4

clojure.core.logic 似乎在步行集上有问题。最小的失败示例：

(run* [q] (== q #{}))

生产

java.lang.StackOverflowError at clojure.core.logic.Substitutions.walk(logic.clj:344) at clojure.core.logic$walk_STAR_$fn_ 2633.invoke(logic.clj:216) at clojure.core.logic$eval2838 $fn _2839.invoke(logic.clj:956) at clojure.core.logic.protocols$eval1389$fn_ 1390$G _1380__1397.invoke(protocols.clj:55) at clojure.core.logic$walk_STAR_.invoke(logic. clj:214) at clojure.core.logic$walk_STAR_$fn_ 2633.invoke(logic.clj:218) at clojure.core.logic$eval2838$fn _2839.invoke(logic.clj:956) at clojure.core.logic .protocols$eval1389$fn_ 1390$G _1380__1397.invoke(protocols.clj:55) at clojure.core.logic$walk_STAR_.invoke(logic.clj:214) at clojure.core.logic$walk_STAR_$fn_2633.invoke(logic.clj:218) at clojure.core.logic$eval2838$fn _2839.invoke(logic.clj:956) at clojure.core.logic.protocols$eval1389$fn_ 1390$G _1380__1397.invoke(protocols .clj:55) 在 clojure.core.logic$walk_STAR_.invoke(logic.clj:214) 在 clojure.core.logic$walk_STAR_$fn_2633.invoke (logic.clj:218) 在 clojure.core.logic$eval2838 $fn _2839.invoke(logic.clj:956) at clojure.core.logic.protocols$eval1389$fn_ 1390$G _1380__1397.invoke(protocols.clj:55)

为什么这会生成 Stackoverflow？与空向量/列表/地图/其他类型统一按预期工作。

4

2 回答 2

7

您从 core.logic 的原始作者那里得到了不支持集合的答案，但我认为您本可以将您的问题表述为更具领先性，并且可能已经获得了关于为什么不支持集合的更有趣的回答（尚未) 或可能需要什么来支持他们。至于为什么，我怀疑它们确实不需要，因为distincto并permuteo提供了可用于测试集合属性的目标。至于在统一中支持它们可能需要什么，请按照下面的粗略、丑陋、不完整和低效的初看。

发生堆栈溢出是因为集合是集合，并且集合在行走时被递归到。但是由于不支持集合，因此集合没有 walk 实现，并且对象的默认设置是返回自身。最终结果是，从步行集的角度来看，它们包含自己，并且堆栈被炸毁，试图递归到底部。

在查看源代码的同时加入我的 REPL ，让我们一起破解一些东西。

(use 'clojure.core.logic)
(use 'clojure.core.logic.protocols)

让我们告诉 core.logic 使用现有的序列实现来遍历集合。

(extend-protocol IWalkTerm 
  clojure.lang.IPersistentSet 
  (walk-term [v f] (with-meta (set (walk-term (seq v) f)) (meta v))))

(run* [q] (== q []))
;=> ([])
(run* [q] (== q #{}))
;=> (#{})

目前很好...

(run* [q] (== q [1 2 3]))
;=> ([1 2 3])
(run* [q] (== q #{1 2 3}))
;=> (#{1 2 3})

一致，但不是非常有用

(run* [q] (== [1 q 3] [1 2 3]))
;=> (2)
(run* [q] (== #{1 q 3} #{1 2 3}))
;=> ()
(run* [q] (== #{1 3 q} #{1 2 3}))
;=> ()

现在我们有一个问题。最后两个都应该返回(2)，因为集合没有顺序，但都没有返回结果。我们还需要告诉 core.logic 如何统一集合。让我们偷懒，尝试用现有permuteo来传达缺乏秩序。

(extend-protocol IUnifyTerms 
  clojure.lang.IPersistentSet 
  (unify-terms [u v s] (bind s (permuteo (seq u) (seq v)))))

(run* [q] (== #{1 q 3} #{1 2 3}))
;=> (2)
(run* [q] (== #{3 1 q} #{1 2 3})) 
;=> (2)

出色的！

(run* [q] (fresh [a1 a2 a3] (== #{a1 a2 a3} #{1 2 3}) (== q [a1 a2 a3])))
;=> ([1 2 3] [2 1 3] [1 3 2] [3 1 2] [2 3 1] [3 2 1])

很酷。

(run* [q] (== #{1 2 [3 q]} #{1 2 [3 4]}))
;=> (4)

不错……但是

(run* [q] (== #{1 2 #{3 q}} #{1 2 #{3 4}}))
;=> IllegalArgumentException No implementation of method: :walk of protocol:  #'clojure.core.logic.protocols/ISubstitutions found for class: clojure.core.logic$permuteo$fn...

所以我们使用 有点太草率了permuteo，让我们试着用它来clojure.math.combinatorics代替

(use 'clojure.math.combinatorics)

(extend-protocol IUnifyTerms 
  clojure.lang.IPersistentSet 
  (unify-terms [u v s]
    (when (set? v)
      (let [u (seq u)
            v (seq v)]
        (reduce #(mplus % (-inc %2)) 
                (for [p (permutations u)] (unify s p v)))))))

现在...

(run* [q] (== #{1 2 #{3 q}} #{1 2 #{3 4}}))
;=> 4

(run* [q] (== #{ #{ #{q} :bar} :baz}  #{:baz #{:bar #{:foo} } }))
;=> (:foo)

看起来很有希望。

于 2013-08-06T21:16:12.323 回答
2

core.logic 中不支持集合。

于 2013-08-02T21:46:33.847 回答