lisp - 如何在 LISP 中为 R 关系创建传递函数？

Question

构造传递自反闭包R*。二元关系 R = {(1,1), (1,2), (2,1), (2,2), (3,1), (3,4), (4,1), (4 ,2), (4,4)}

Answer 1

我们可以做的是将数据转换成某种图形结构，例如邻接哈希表。然后我们可以遍历它并回填缺失的传递和自反关系。

TXR Lisp 程序:

;; association data
(defvar rel-pairs '((1 1) (1 2) (2 1) (2 2) (3 1) (3 4) (4 1) (4 2) (4 4)))

;; turn data into hash table associating each domain value
;; with its range values.
(defvar rel [group-reduce (hash) car (op cons (cadr @2) @1) rel-pairs])

(defun ensure-trans-reflex (hash)
  ;; ensure reflexivity: if [hash key] maps to some values,
  ;; each of those values should appears as keys mapping
  ;; back to the key.
  (dohash (key values hash)
    (each ((val values))
      (pushnew key [hash val])))

  ;; ensure transivity: individually starting at each
  ;; key in the hash, we recursively traverse the graph,
  ;; and associate that key with values thus reachable.
  (dohash (key values hash hash)
    (let ((visited (hash)))
      (labels ((transitivize (key value)
                 (each ((next-val [hash value]))
                   (when (test-set [visited next-val])
                     (pushnew next-val [hash key])
                     (transitivize key next-val)))))
        (each ((val values))
          (transitivize key val))))))

(prinl rel)
(ensure-trans-reflex rel)
(prinl rel)

输出:

$ txr rel.tl 
#H(() (1 (2 1)) (2 (2 1)) (3 (4 1)) (4 (4 2 1)))
#H(() (1 (4 3 2 1)) (2 (3 4 2 1)) (3 (2 3 4 1)) (4 (3 4 2 1)))

基本上，示例数据最终将每个键与每个键(包括它自身)相关联。