ラケット入れ子リストとそれらに関数を適用する

Question

私はラケットを教えようとしています。私は現在、ネストされたリストを理解するのに役立つ関数を書こうとしています。この関数は、ネストされたリストとプロシージャを取り、そのプロシージャを各要素に適用して新しいリストを生成します。例：

(map-tree even? '(1 2 3 4)) => '(#f #t #f #t) 

ここで私はこれまで持っているものです：

(define (map-tree proc tree) 
    (map-tree-aux tree proc '())) 

(define (map-tree-aux tree proc lst) 
(if (null? tree) 
    lst 
    (if (list? tree) 
     (if (null? (cdr tree)) 
      (if (number? (car tree)) 
        (map-tree-aux (car tree) proc (append-end (proc (car tree)) lst)) 
        (map-tree-aux (car tree) proc lst)) 
      (if (number? (car tree)) 
        (map-tree-aux (cdr tree) proc (append-end (proc (car tree)) (map-tree-aux (car tree) proc lst))) 
        (map-tree-aux (cdr tree) proc lst))) 
     lst))) 

(define (append-end elem lst) 
    (append lst (list elem))) 

これは私が供給元の例で動作しますが、より複雑な例が間違って出てくる：

(map-tree even? '(1 (2 (3 (4))))) should be '(#f (#t (#f (#t)))), but is currently (#f #t #f #t). 

私はそれがちょうど問題がどこかの "上場"されていることを知っていますが、私はそれを行う方法を見つける問題があります。私が最初に考え

は（結果のリストは反対方向にネストされている）の木がnullで、(car tree)は番号ではありませんが、私は私が何をしたいの反対を得ればlstにlist手順を適用することでした。私は本当にあなたの助けに感謝します。

ありがとうございます！

Answer 1

リストのリストを反復処理すると、場合によっては、確認するための一般的な考え方は次のとおりです。

• リストが空(null? lst)であれば、リストの最初の項目がある場合、何か ...
• を行いますアトミック(not (pair? (car lst)))、何か他を行う...
• リストの最初の項目がリスト自体(pair? (car lst))であれば、そうでない ...

Choosing the right constructも重要です。入れ子のifの代わりに、condまたはmatchなどを使用してください。

効率を向上させるために、再帰的な手順で一定でない手順（例：append）を使用しないようにしてください。念頭に置いてこれらにより

---

、問題の関数を作成するための一つのアプローチは、単に古いの構造を維持しながら、次のように、新しいリストを作成しconsを使用することです：

(define (my-map pred lst) 
    (cond 
    ((null? lst) '()) 
    ((not (pair? (car lst))) 
    (cons (pred (car lst)) 
      (my-map pred (cdr lst)))) 
    (else 
    (cons (my-map pred (car lst)) 
      (my-map pred (cdr lst)))))) 

あなたがすることができますmatch代わりのcondを使用して同じ機能を記述します。

(define (my-map pred lst) 
    (match lst 
    ['() '()] 
    [(cons (? pair?) b) 
    (cons (my-map pred (car lst)) 
      (my-map pred (cdr lst)))] 
    [(cons a b) 
    (cons (pred (car lst)) 
      (my-map pred (cdr lst)))])) 

ます。またトンを行う末尾再帰関数を構築することができます彼：

(define (my-map pred lst) 
    (let loop ((lst lst) 
      (acc '())) 
    (cond 
     ((null? lst) 
     (reverse acc)) 
     ((not (pair? (car lst))) 
     (loop (cdr lst) (cons (pred (car lst)) acc))) 
     (else 
     (loop (cdr lst) (cons (loop (car lst) '()) acc)))))) 

アキュムレータaccに建設されたリストは、元のリストlstから逆の順序であるため、(reverse acc)は、基本ケースで返されていることに注意してください。これを避けるために、我々はにこの機能を変更することができる代わりに、継続累積：これは期限を過ぎている

(my-map even? '(1 2 3 4 5 7)) 
=> '(#f #t #f #t #f #f) 
(my-map even? '(1 (2 (3 (4 (5 (7))))))) 
=> '(#f (#t (#f (#t (#f (#f))))))