- Code: Select all
(defun relation-composition (a b)
(if (null a) nil
(let ((rest (relation-composition (cdr a) b)))
#'(lambda (x) (member x rest))
(list (caar a) (cadr x)))
(not (equal (car x) (cadar a)))) b))) rest))))
Hi, this *shouldn't be* very difficult, but I'm still not sure. Will the above algo compose two relations in the most efficient way? Relation for this matter is described as a list having sub-lists, which, in turn, contain exactly two elements. The relations are well-formed (i.e. there are no repetitions). The first element of sub-list of the first list is a member of set A, the second element of the sub-list of the first list is the element in the set B. The first element of the sub-list of the second list is the element in the set B, the second element of the sub-list of the second list is the element of the set C. The composition of relations is defined as a list containing sub-lists where first element a of the sub-list is the member of set A, and the second element c of the sub-list is the member of set C, such that first relation contains the pair (a b) and the second relation contains the pair (b c).
A practical example would be the composition of relation of being a parent with itself, where the resulting relation would be the relation of being a great-parent of.