1

受講しているコースの一部としてスキームを使用しています。宿題で高階関数を使うように言われました。ただし、この指示はやや不明確なようです。

高次手続きの考え方がよくわかりません。再帰を使用してすべての質問を行うことができますが、それは同じことです。再帰関数と高次の手順で記述された関数の例で、誰でも説明できますか。

2番目の質問として：

例: 奇数をすべて取得しようとする

を使用することもできます(flatten (map odd ((1 4 5) (4 5 1 4 9))))が、ネストされたリストがある場合は、次のようにネストされたリストで map を使用できますか?

(flatten (map odd ((1 3 (9 5 7)))); これには機能がありますか、それを行うためのきれいな方法はありますか?

4

1 に答える 1

2

高階関数のポイントは、コード内のボイラープレートを削減し、ループ (技術的には再帰ですが、その目的はループであるため、そのように言及します) と実際のロジックの間の結合を減らすことです。例を次に示します (すべての奇数を再取得します): 手動ループは次のようになります。

(define (filter-odd lst)
  (cond ((null? lst) '())
        ((odd? (car lst)) (cons (car lst) (filter-odd (cdr lst))))
        (else (filter-odd (cdr lst)))))

しかし、ループとフィルタリングが 1 つの関数で行われていることに注意してください。これらの 2 つの無関係な操作が結合されているため、関数が何を行っているかを把握するのが難しくなります。高レベル関数を使用すると、別の方法で実行できます。

(define (filter pred lst)
  (cond ((null? lst) '())
        ((pred (car lst)) (cons (car lst) (filter pred (cdr lst))))
        (else (filter pred (cdr lst)))))

(define (filter-odd lst)
  (filter odd? lst))

odd?ここで、が に分離されたループ ロジックからどのように分離されているfilterかに注目してください。filterアイテムを保持するかどうかを決定する関数オブジェクトを受け取るようになり、 の呼び出し元filterは、選択した任意の関数を挿入できます。

これが高階関数の意味です。これは、関数オブジェクトをパラメーターとして取り、その操作をカスタマイズする関数です。

あなたの質問の元の編集で述べたように、map別の高次関数ですが、リストからアイテムをフィルタリングする代わりに、元のリスト内のすべてのアイテムの変換を返します。特定の変換は、mapの呼び出し元によってパラメータ。

フラット化などに関する実際の質問に答えるに(map filter-odd '((1 3 (9 5 7))))は、 を呼び出した結果である単一のアイテムを含むリストが返され(filter-odd '(1 3 (9 5 7)))ます。いいえ、mapあなたのためにサブリストに再帰しません（そしてどちらもしませんfilter）。

ただし、最初に入力を平坦化して (とにかく出力を平坦化するため)、それfilter-oddを直接呼び出すことができます。期待どおりの結果が得られることを願っています。

（（述語）と混同される可能性が低いため、名前を your に変更oddしました。）filter-oddodd?

おまけ素材

ちなみに、filterとmapは両方とも、フォールド (より具体的には右フォールド) と呼ばれる、より一般的な高階関数の特殊化です。filter折り畳みは、またはでは対応できないことを表現できますmapが、何らかの形でリスト内のすべての項目をトラバースする必要があります。lengthフォールドとして表現された関数の例を次に示します。

(define (foldl func init lst)
  (if (null? lst) init
      (foldl func (func (car lst) init) (cdr lst))))

(define (length lst)
  (foldl (lambda (elem count)
           (+ count 1))
         0 lst))

ここでの利点は、length関数がリストのトラバースについて心配する必要がないことです。これはフォールドによって処理されます。各反復で何をすべきかを気にする必要があるだけです (ここでは、count0 から始まる に 1 を追加するだけです)。

この場合、左からトラバースしても右からトラバースしても長さは同じであり、Scheme では左からトラバースした方がスペース効率が良いため、その方が好ましい。mapただし、 andを実装するにfilterは、右折が必要です (そうしないと、要素が逆になります。以下の関数でfoldrwithfoldlを置き換えてみてください)。

(define (foldr func init lst)
  (if (null? lst) init
      (func (car lst) (foldr func init (cdr lst)))))

(define (map func lst)
  (foldr (lambda (elem result)
           (cons (func elem) result))
         '() lst))

(define (filter pred lst)
  (foldr (lambda (elem result)
           (if (pred elem)
               (cons elem result)
               result))
         '() lst))
于 2012-10-07T03:53:08.557 に答える