2

ネストされたリストの各値に関数を適用するスキームでマッピング関数を記述しようとしています。

たとえば、(map number? '(3 (2 A) 2 Z)返す必要があります(#t (#t #f) #t #f)

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

(define (map fun lst)
    (if (null? lst) '()
        (if (list? (car lst)) 
            (cons (map fun (car lst)) (map fun (cdr lst)))
                 (cons (fun (car lst)) (map fun (cdr lst))))))

ネストされたリストがリストの先頭にある場合に機能します。たとえば、(map number? '((3 A) 2 Z))正しく戻ります((#t #f) #t #f)

この問題は、ネストされたリストが元のリストの別の要素の後にある場合に発生します。たとえば、(map number? '(3 A (2 Z)))誤って(#t #f #f)[結果は(#t #f (#t #f))]を返します。

これを修正するためにアルゴリズムを変更するにはどうすればよいですか?

4

2 に答える 2

4

これが私の解決策です---デコレータパターンmapを使用して、組み込みを再利用するという点で非常に安価です。（私は知っています、デザインパターンを使用するSchemeプログラム？:-O）

(define (deep-map f l)
  (define (deep x)
    (cond ((null? x) x)
          ((pair? x) (map deep x))
          (else (f x))))
  (map deep l))

letこれは、名前付き：を使用することでさらに「簡略化」できます。

(define (deep-map f l)
  (let deep ((x l))
    (cond ((null? x) x)
          ((pair? x) (map deep x))
          (else (f x)))))

（2つのコードスニペットは同一ではありませんが、この質問では、入力としてリストを指定すると、両方とも同じように機能します。）

およびチェック（両方ともO（1））はnull?、（O（n））pair?の使用を回避するために使用されます。list?

于 2011-04-18T08:22:31.870 に答える
3

あなたのコードは正しいですが、実際よりも冗長すぎます。ヒント: 2 つのケースのみを考慮する必要があります:lstが a であるかどうかですpair?。それで全部です。言い換えれば、コードは入力が常にリストであると想定していますが、単純化して何でも受け入れ、ペアの場合に特別な再帰的なことを行うことができます。

あなたが見ている問題については、私の推測では、あなたは Racket を使用しているため、奇妙なケースに直面していると思います。そうでない場合は、ここで読むのをやめてください。

問題は、Racket では、へのバインドmapが行われる前に関数自体がコンパイルされるため、map呼び出しは実際には再帰的ではなく、組み込みの呼び出しにすぎないということですmap。後でmap、結果の関数に (再) バインドされますが、再帰呼び出しは既にコンパイルされています。同じ定義を 2 回入力すると、再び機能することがわかります。これを解決する方法は、REPL で動作しないようにすることです。代わりに、常に some で始まるファイルに定義を記述します#lang <something>。

于 2011-04-18T07:52:56.920 に答える