1

ラムダを使用して、数値のリストを消費し、各数値の最初の出現以外のすべてを削除する関数を作成するように求める割り当ての質問があります。私の関数は、間違った結果を生成することを除いて、非常に優れていると思います! 各数値の最後の出現を含むリストを生成します。適切なリストと同じ値を持つリストを生成しますが、順序が異なります。これが私のコードです：

    (define (remove-duplicates numlist)
      (foldr (lambda (a b) 
               (cond
                 [(not (member? a b)) (cons a b)]
                 [else b])) empty numlist))

foldlの代わりに使用してみましfoldrたが、驚くことではありませんが、正しいリストが生成されますが、逆になります。foldl別のラムダ式で作成されたリストを逆にすることに頼らずに、正しいリストを作成する方法はありますか?

これは宿題なので、明確な回答はしないでください。

みんな、ありがとう！

4

1 に答える 1

1

foldrが意味的にどのように動作するかを考えてください。リストの右端の要素から開始し、左に移動して折り畳みを実行します。つまり、ラムダ関数でaは、これまでに折りたたまれたリストのすぐ左にある要素をb表し、リスト要素の右側にすべてを折りたたんだ結果を表しますa。これを念頭に置いて、次のことを考慮してください。

[(not (member? a b)) (cons a b)]
[else b]

リストbにすでにが含まれているかどうかを確認しますa。もしそうなら、あなたはそれをそのままにして捨てaますb。これは、コードが最初ではなく最後の（右端の）出現を保持する理由を説明しています。正しいフォールドを実行したい場合は、ロジックを変更する必要があります。bあなたはそれが含んでいる問題のある要素をどういうわけか「パージ」する必要がありaます。

[(not (member? a b)) (cons a b)]
[else (cons a (purge a b))]

このようにして、最終的には、各一意の要素の右端ではなく、左端の出現のみを保持します。両方ともリストをトラバースする必要があるためmember?、同時に実行するのが賢明かもしれません。purgeこれには、追加のリファクタリングが必要になります。

関数はとにかくO（n 2）時間を要するので、バージョンにO（n）を逆に追加することは、実際には時間の複雑さを損なうことはないことに注意してください。foldl

于 2011-11-19T22:03:35.640 に答える