- 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.