Let's say we have this parent/child hierarchy:
(derive ::integer ::decimal)
(derive ::positive-integer ::integer)
(derive ::long ::integer)
What is a Clojure idiomatic to implement a way to find the lowest common ancestor in such a hierarchy? I.e.:
(lca ::positive-integer ::long) ; => ::integer
My initial thoughts include using a recursive function traversing combinations of parents of each argument, but I suspect there probably is a better approach.
My motivation is to use this as a dispatch function for a multimethod that takes 2 arguments and dispatches to the best suited implementation based on the types of the arguments.
The function ancestors returns a set, so you'll want to (require [clojure.set :as s]).
Now write:
(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)))
Let's try it out!
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
Here's how it works: I take the set of ancestors of each type using ancestors. I add the type itself to the resulting set (since I think (lca ::integer ::long) should return integer instead of decimal) using conj, for both types. Using set intersection, I store all common ancestors into the variable ac.
Of the common ancestors, I want to know which one of those has the most ancestors. (comp count ancestors) is a function which takes one type and returns the number of ancestors it has. I partially apply max-key to this function, and then I apply (using apply) the resulting function to the collection ac. The result is the common ancestor with the greatest number of ancestors, or the least common ancestor.
(Note that lca will give an error if you pass it two types without any common ancestors! You should decide how to handle this case yourself.)