使用遞歸與球拍返回列表

我想從具有雙遞歸的方法返回一個列表（BST，二叉搜索樹）。我想實現它如下：使用遞歸與球拍返回列表

(define (mapBST BST someFunct) 
    (cond 
    [(null? BST) 
    '()] 
     [else (cons (car BST) (someFunct (car (cdr BST)))) (mapBST (car (cdr (cdr BST))) someFunct) (mapBST (car (cdr (cdr (cdr BST)))) someFunct) ] 

) 
)

調用此方法與此代碼小片段

(define bst 
      '(3 "3" 
        (1 "1" 
        () 
        (2 "2"()()) 
       ) 
        (5 "5"()()) 
      ) 
) 
(mapBST bst string->number)

我也試過這個片段，但它返回((()())())：

[else (printf (car (cdr BST))) (cons (mapBST (car (cdr (cdr BST))) someFunct) (mapBST (car (cdr (cdr (cdr BST)))) someFunct)) ]

的結果應該返回相同的BST，但使用數字而不是字符串作爲值。

來源

2017-04-18 Comp_Sci_Student

顯示您要調用的代碼，它生成的內容以及您期望生成的內容。正確縮進代碼，在新行上啓動每個子表達式。提示：在'[else A B C]'中，'A'和'B'沒有效果 - 它們的值被忽略，只返回最後一個值。 –

在你的else表達式中，你沒有正確重構二叉搜索樹，這就是爲什麼你得到一個空列表。您else情況下更改爲

... 
[else 
(cons (car BST) 
     (cons (someFunct (car (cdr BST))) 
      (cons (mapBST (car (cdr (cdr BST))) someFunct) 
        (cons (mapBST (car (cdr (cdr (cdr BST)))) someFunct) empty))))] 
...

或

... 
[else 
(list (car BST) 
     (someFunct (car (cdr BST))) 
     (mapBST (car (cdr (cdr BST))) someFunct) 
     (mapBST (car (cdr (cdr (cdr BST)))) someFunct))] 
...

將解決您的問題（這兩個選項產生相同的名單，因爲(cons 1 (cons 2 empty))相當於(list 1 2)）。

這裏是mapBST完全更新：

(define (mapBST proc BST) 
    (cond 
    [(null? BST) empty] 
    [else 
    (list (car BST) 
      (proc (cadr BST)) 
      (mapBST proc (caddr BST)) 
      (mapBST proc (cadddr BST)))]))

例如，

(define BST '(3 "3" (1 "1"() (2 "2"()())) (5 "5"()()))) 
(mapBST string->number BST) 
=> '(3 3 (1 1() (2 2()())) (5 5()()))

來源

2017-04-18 07:43:30 assefamaru

正如另一個答案指出的那樣，你實際上並沒有返回你是else子句中你認爲什麼。修復這將使您的程序工作。然而，這種類型的人在過去的六十年代曾經習慣編寫Lisp，並且正確地讓Lisp變成了一個不好的名字，因爲它是完全不透明的。使用像caddr這樣的東西比較好，但只是稍微有點（它們的語言提供了多少呢？我永遠不會記得）。不過更好的，如果你的數據在概念上的列表，是利用函數名，像first & second，因爲他們說什麼，你居然意味着（如果你的數據在概念conses之外的一棵樹，然後car & c是更好的可能）。但他們仍然有'本週有多少人'的問題。

正確的解決方案是使用解構& /或模式匹配來根據數據的形狀綁定變量。這使你的代碼真正清晰。球拍有一個全面的機制，我不是很瞭解細節，但我知道足夠讓我通過。這裏是你的功能（固定）版本，它使用match做的工作：

(define (map-bst bst fn) 
    (match bst 
    ['() '()] 
    [(list 1st 2nd 3rd 4th) 
    (list 1st 
      (fn 2nd) 
      (map-bst 3rd fn) 
      (map-bst 4th fn))] 
    [_ (error "botch")]))

（注意，這可能會提供更好的變量名做：我不知道是什麼結構的各個位的意思）。

來源

2017-04-18 09:12:53 tfb

使用遞歸與球拍返回列表

回答

相關問題