2

假设我们有这个父/子层次结构：

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

什么是 Clojure 惯用的实现在这种层次结构中找到最低共同祖先的方法？IE：

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

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

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

4

1 回答 1

1

该函数ancestors返回一个集合，因此您需要(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)应该返回integer而不是返回decimal）conj这两种类型。使用集合交集，我将所有共同的祖先存储到变量ac中。

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

（请注意，lca如果您将两种类型传递给它而没有任何共同的祖先，则会出现错误！您应该自己决定如何处理这种情况。）

于 2016-01-21T21:03:51.353 回答