Code: Select all
(defun relation-composition (a b)
(if (null a) nil
(let ((rest (relation-composition (cdr a) b)))
(append
(remove-if
#'(lambda (x) (member x rest))
(mapcar
#'(lambda (x)
(list (caar a) (cadr x)))
(remove-if
#'(lambda (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.