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)