A recursive solution could be something like this:Quote from: "ralph.ronnquist"
(define (trans s (x s) (f (and s (curry intersect (first s)))))Code Select
(if s (trans (rest s) (cons (unique (flat (filter f x))) (clean f x))) x))
Perhaps there is something faster.
Looks good, Ralph! I don't think I could do it faster. I prefer your code anyway because it's understandable.
This is what I see. The input
So, for instance, the first member of your example input (13 1) implies both 13R1 and 1R13 (when example input describes R). This is because, I don't see the input to
Now, when looking at the input set instead as a set of "links" of a graph (as you described them), then your function
The recursive step of
When I use your
Code Select
(define (make-symmetric-relation S)
(letex ([S] S)
(fn (x y)
(exists (fn (s) (and (member x s) (member y s)))
'[S]))))
Here's a terrible test that shows it in action.
Code Select
(define (test-trans input x y)
(let (R (make-symmetric-relation input)
Rt (make-symmetric-relation (trans input))
yesno (fn (x) (if x 'yes 'no)))
(list ;; is (x,y) in the original relation?
(yesno (R x y))
;; is (x,y) in the transitive closure?
(yesno (Rt x y)))))
For instance, (8 15) is in the original relation; so, it will also be in the transitive closure. (9 13) is not in the original relation, but it is in the transitive closure. (9 15) is in neither.
Code Select
> (define input
'((13 1) (9 19) (4 13) (4 12) (15 8) (3 15) (7 5) (9 4) (11 0) (0 5)))
> (test-trans input 8 15)
(yes yes)
> (test-trans input 9 13)
(no yes)
> (test-trans input 9 15)
(no no)
Thanks again! Your function is now added to my quiver! :)