Chicken计划中的拓扑排序错误？

Question

#;2> (topological-sort 
'((i am) 
    (not trying) 
    (confuse the) 
    (am trying) 
    (trying to) 
    (am not) 
    (trying the) 
    (to confuse) 
    (the issue)) 
    eqv?) 
(not i am trying to confuse the issue) 

订购这样子列表可以更清楚正确的输出应该是什么：

(i am) 
    (am not) 
    (not trying) 
    (trying to) 
    (to confuse) 
    (am trying) 
    (confuse the) 
    (trying the) 
    (the issue) 

看来，为了应该是：

i am not trying to confuse the issue 

这是一个错误，还是我错过了什么？

----编辑：----

结合子列表与普通头：

(topological-sort 
'((i am) 
    (not trying) 
    (confuse the) 
    (am trying not) 
    (trying to the) 
    (to confuse) 
    (the issue)) 
    eqv?) 

(i am not trying to confuse the issue) 

如此看来正确的做法是预处理输入 以确保没有两个子列表共享相同的头。

解决罗塞塔代码拓扑排序问题：

(use srfi-1) ; list operators 
(use srfi-69) ; hash-tables 

(define data 
'((des_system_lib std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee) 
    (dw01    ieee dw01 dware gtech) 
    (dw02    ieee dw02 dware) 
    (dw03    std synopsys dware dw03 dw02 dw01 ieee gtech) 
    (dw04    dw04 ieee dw01 dware gtech) 
    (dw05    dw05 ieee dware) 
    (dw06    dw06 ieee dware) 
    (dw07    ieee dware) 
    (dware   ieee dware) 
    (gtech   ieee gtech) 
    (ramlib   std ieee) 
    (std_cell_lib  ieee std_cell_lib) 
    (synopsys))) 

(define table (make-hash-table)) 

(for-each 
    (lambda (xs) 
    (let ((head (car xs)) (tail (cdr xs))) 
     (for-each 
     (lambda(key) 
      (when (not (eqv? key head)) 
      (hash-table-update!/default 
       table key (lambda (accum) (cons head accum)) '()))) 
     tail))) 
    data) 

(define answer 
    (topological-sort (hash-table->alist table) eqv?)) 

answer 

一个可能的结果（因为哈希表是无序的，它可能 每次是不同的）：

(std ieee dware dw05 dw06 dw07 ramlib std_cell_lib gtech synopsys 
dw02 dw01 des_system_lib dw03 dw04) 

尝试验证回答：

(any 
    (lambda (tail) 
    (any 
     (lambda (key) 
     (and (hash-table-exists? table key) 
      (member (car tail) (hash-table-ref table key)))) 
     (cdr tail))) 
    (reverse (pair-fold cons '() answer))) 

#f 

这似乎是正确的。

Answer 1

是的，这是一个已知的bug：

#1185 (wrong sorting example for topological-sort)