1

(filter procedure list)procedureの各要素に適用されlist 、true を返す要素のみを含む新しいリストをprocedure 返します。
( R. Kent Dybvig The Scheme Programming Language ) (オンライン)

この説明から明らかでないことは、返されるリスト内の要素が と同じ順序で発生する一方で、listの呼び出しの順序がprocedureR6RS で指定されていないことです。(ただし、Racket は「最初から最後まで各要素に」という手順を適用します)

最近アクティブな回答filterfuncでは、引数リスト を順番に 処理する必要があることが言及されています。この関数はどのように記述すればよいでしょうか?

問題の説明を含む回答が提供されます。

4

2 に答える 2

2

Scheme 実装が使用する順序とその理由は? 試してみましょう (すべてのコードは Chez Scheme REPL で実行されます):

  1. アプリケーションの表示順
> (filter (lambda (x) (display x) (even? x))
    '(0 1 2 3 4 5)))
452301(0 2 4)
>
  1. なぜこの注文？
    R6RS 実装は、それが適切なリストであることを確認する必要がありますlist
  • 空のリストで終わります:
> (filter (lambda (x) (display x) (even? x))
    '(0 1 2 . 3)))
Exception in filter: (0 1 2 . 3) is not a proper list
>
  • 循環性なし:
> (define xs '(0 1 2 3))
> (set-cdr! (cdddr xs) (cdr xs))
> (filter (lambda (x) (display x) (even? x)) xs)
Exception in filter: (0 1 2 3 1 2 ...) is not a proper list
>
  • filterフィルタリング中にこれらの要件をチェックし、述語アプリケーションの「452301」の順序をもたらす in Chez Schemeの実装は、ここ
    で見ることができます (行 589-617: ソースをスクロールする代わりに、以下のスポイラーとしてバージョンが含まれています) githubで）
  1. 何？
    Chez Scheme コードは、「亀とウサギ」アルゴリズムを使用 してサイクルを検出します。エラー チェックがなければ、コードは次のようになります。
> (let ([filter
    (lambda (pred? ls)
      (let f ([fast ls])
        (if (pair? fast)
          (let ([rest (f (cdr fast))])
            (if (pred? (car fast))
              (cons (car fast) rest)
              rest))
          '())))])
  
    (filter (lambda (x) (display x) (even? x))
      '(0 1 2 3 4 5)))
543210(0 2 4)
>

(識別子fastは、Chez スキーム コードと一致させるために使用されます。それ以外の場合もありlsます)

  1. これをどのように変更してpred?「最初から最後まで」呼び出すことができますか?
  • 変数をアキュムレータに置き換えrestます (以下を上記の 3 と比較してください。変更は小さいですが、フィルター処理された要素はconsacc に編集されるため、結果を得るには逆にする必要があります)。
> (let ([filter
    (lambda (pred? ls)
      (let f ([fast ls] [acc '()])
        (if (pair? fast)
          (f (cdr fast)
             (if (pred? (car fast))
               (cons (car fast) acc)
               acc))
          (reverse acc))))])
  
    (filter (lambda (x) (display x) (even? x))
      '(0 1 2 3 4 5)))
012345(0 2 4)
>

したがって、必要な として 4 を使用できますfilterfunc。Chez スキームの実装のようなエラー チェックを追加することは興味深い演習になるでしょう。これは効果的です。

(define (filter pred? ls)
(unless (procedure? pred?)
(error #f "not a procedure" pred?))
(or (let f ((pred? pred?) (fast ls) (slow ls))
(if (pair? fast)
(let ((fast1 (cdr fast)))
(if (pair? fast1)
(and (not (eq? fast1 slow))
(let ((fast2 (cdr fast1)))
(let ((rest (f pred? fast2 (cdr slow))))
(and rest
(if (pred? (car fast))
(if (pred? (car fast1))
(if (eq? rest fast2)
fast
(list* (car fast)
(car fast1) rest))
(cons (car fast) rest))
(if (pred? (car fast1))
(if (eq? rest fast2)
fast1
(cons (car fast1) rest))
rest))))))
(and (null? fast1)
(if (pred? (car fast))
fast
'()))))
(and (null? fast) '())))
(error #f "circular/improper list" ls)))

于 2021-12-03T12:40:49.480 に答える