Racketで再帰を使用してリストを返す

Question

二重再帰を持つメソッドからリスト（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を返しますが、stringではなく数値を値として返します。

Answer 1

他の表現の中で、バイナリ検索ツリーを正しく再構成していないため、空のリストが表示されています。 （(cons 1 (cons 2 empty))が(list 1 2)と同等であるため、両方のオプションは、同じリストを生成し、）

... 
[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))] 
... 

にごelseケースを変更すると、あなたの問題を解決します。ここで

が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()())) 

Answer 2

は、あなたが実際にあなたがelse句であると思います何帰国されていません。修正すると、プログラムが動作します。しかし、この種類の(car (cdr (cdr ...)))は、人々が1960年代にLispを書くのにどのように使用されたのか、まったく不透明であるためLispには悪い名前が付いています。 caddrのようなものを使用するほうが、ほんのわずかです（そして、どれくらいの言語が提供されていますか？私は決して覚えていません）。あなたのデータは、概念的リストであれば、まだ良い、彼らはあなたが実際にを意味するものを言うのでfirst & secondような名前の関数を使用することです（あなたのデータは、概念的コンスの木であるならば、その後、car & Cは、おそらく優れています）。しかし、彼らはまだ「今週は何人いるのか」という問題を抱えています。

正しい解決策は、データの形状に応じて変数をバインドするために、デストラクチャリング& /パターンマッチングを使用することです。これはあなたのコードを実際にはっきりさせます。ラケットにはこのための包括的なメカニズムがありますが、これは私が実際に詳細には分かりませんが、私は十分に理解しています。

(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")])) 

（より良い変数名で行うことができ、この点に注意してください：私は構造体の様々なビットが何を意味するのか分からない）ここで仕事をするためにmatchを使用して、あなたの関数の（固定）バージョンです。