那種奇怪的球拍

的行爲，我有以下定義：那種奇怪的球拍

(struct type (parent dirty) #:mutable #:transparent) 
    (define types (make-hash)) 

    (define (add-key predicate parent) 
     (begin 
     (hash-ref! types parent (type empty #t)) ;;if the parent doesn't exist, is created with no parent. 
     (let([node (hash-ref types predicate #f)]) 
      (if(or (boolean? node) ;;the node is not on the list 
       (not(equal? (type-parent node) parent))) ;;the node has a different parent 
      (hash-set! types predicate (type parent #t)) 
      (printf "nothing to do\n") 
      )))) 

    (define (ancestor? predicate1 predicate2) 
     (let ([node (hash-ref types predicate2 #f)]) 
     (cond [(false? node)(error "following predicate is not in types: " predicate2)] 
       [(empty? (type-parent node)) #f] 
       [(equal? (type-parent node) predicate1) #t] 
       [else (ancestor? predicate1 (type-parent node))])))

看來工作非常好，我可以做的東西，如：

> (ancestor? integer? even?) 
    #t 
    > (ancestor? list? even?) 
    #f 
    > (ancestor? integer? odd?) 
    #t 
    >

我似乎只是有一個問題與sort as (sort '(integer? odd? number? list? even?) ancestor?) 會拋出以下錯誤：following predicate is not in types: integer? 這當然是在我的實現中定義的。事情是，我確定鍵值對存在，我可以操縱它，我可以手動運行代碼ancestor的每一行......我真的很困惑，可能會導致這個......任何想法？

來源

2013-05-10 Carlos Filipe Costa

注：有一個很可愛的算法，允許你做在不斷的查詢時間，如果你在查詢之前對樹進行線性預處理。請參閱：http://stackoverflow.com/questions/10310809/check-if-2-tree-nodes-are-related-ancestor-descendant-in-o1-with-pre-process – dyoo 2013-05-11 03:14:24

更仔細地讀你的問題：當你說'（sort'（integer？odd？number？list？even？））'，你真的是指'（sort（list integer？odd？number？list？even？））'？ – dyoo 2013-05-11 03:18:59

我把你的代碼保持原樣並將其放在一個文件中。
增加了一個跡線ancestor?：要麼添加第一線與(displayln `(ancestor? ,predicate1 ,predicate2))或添加(trace ancestor?)（一個(require racket/trace)之後）。
這顯示在您的代碼中損壞的違規電話：(ancestor? 'odd? 'integer?)導致該確切的錯誤。

（我不知道你的代碼是這樣做的：這個想法是，可以很容易地機械地推導出這個問題。）

來源

2013-05-10 13:58:49

那種奇怪的球拍

回答

相關問題