parent/child isa 中的最低共同祖先？ Clojure 中的层次结构

Question

假设我们有这个 parent/child 层次结构：

(derive ::integer ::decimal)
(derive ::positive-integer ::integer)
(derive ::long ::integer)

Clojure 惯用语是什么来实现在这种层次结构中查找最低公共祖先的方法？即：

(lca ::positive-integer ::long) ; => ::integer

我最初的想法包括使用递归函数遍历每个参数的 parents 组合，但我怀疑可能有更好的方法。

我的动机是将其用作多方法的分派函数，该多方法采用 2 个参数并根据参数的类型分派到最适合的实现。

Answer 1

函数 ancestors return 是一个集合，因此您需要 (require [clojure.set :as s])。

现在写：

(defn lca [h1 h2]
  (let [a1 (into #{} (conj (ancestors h1) h1))
        a2 (into #{} (conj (ancestors h2) h2))
        ac (s/intersection a1 a2)]
    (apply (partial max-key (comp count ancestors)) ac)))

我们来试试吧！

stack-prj.hierarchy> (derive ::integer ::decimal)
nil
stack-prj.hierarchy> (derive ::positive-integer ::integer)
nil
stack-prj.hierarchy> (derive ::long ::integer)
nil
stack-prj.hierarchy> (lca ::positive-integer ::long)
:stack-prj.hierarchy/integer

工作原理如下：我使用 ancestors 获取每种类型的一组祖先。我将类型本身添加到结果集中（因为我认为 (lca ::integer ::long) 应该 return integer 而不是 decimal），对于两种类型都使用 conj。使用集合交集，我将 all 个共同祖先存储到变量 ac.

中

在共同祖先中，我想知道其中哪一个拥有最多个祖先。 (comp count ancestors) 是一个函数，它采用一种类型，return 是它拥有的祖先的数量。我将 max-key 部分应用到此函数，然后我将结果函数应用（使用 apply）到集合 ac。结果是祖先数量最多的共同祖先，或者最少共同祖先.

（注意 lca 如果你传递两个没有共同祖先的类型会报错！你应该自己决定如何处理这种情况。）

parent/child isa 中的最低共同祖先？ Clojure 中的层次结构

Lowest common ancestor in parent/child isa? hierarchy in Clojure

clojure

lowest-common-ancestor