Наименьший общий предок в родителях/потомках isa? иерархия в Clojure

Допустим, у нас есть эта иерархия родитель/потомок:

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

Что такое идиоматика Clojure для реализации способа поиска низшего общего предка в такой иерархии? То есть:

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

Мои первоначальные мысли включают использование рекурсивной функции, обходящей комбинации parents каждого аргумента, но я подозреваю, что, вероятно, есть лучший подход.

Моя мотивация состоит в том, чтобы использовать это как функцию отправки для мультиметода, который принимает 2 аргумента и отправляет в наиболее подходящую реализацию на основе типов аргументов.


clojure lowest-common-ancestor
person Jindřich Mynarz    schedule 21.01.2016    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Функция 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 выдаст ошибку, если вы передадите ему два типа без каких-либо общих предков! Вы сами должны решить, как поступить в этом случае.)

person WolfeFan    schedule 21.01.2016
comment
Спасибо! Хотя ancestors, вероятно, следует обернуть в set, чтобы intersection не выдавал ошибку при предоставлении списка, созданного conj, равным нулю, когда нет предков. - person Jindřich Mynarz; 22.01.2016
comment
Почему вы используете into #{} вместо set? - person Jindřich Mynarz; 22.01.2016
comment
Кстати, спасибо, что познакомили меня с max-key! Я использую Clojure уже пару лет, но еще не сталкивался с этой функцией. - person Jindřich Mynarz; 22.01.2016
comment
Я привык использовать into в качестве функции перехода для преобразования одного типа коллекции в другой. set работает в этом случае так же хорошо; это просто не мой стиль. - person WolfeFan; 22.01.2016