フィルタはどのように実装されていますか？

Question

scheme関数を使用してこの関数のヘルプが必要です 与えられた述語を満たす任意のリストのすべての要素を含むリストを返します。たとえば、(filter (lambda (x) (< x 5)) '(3 9 5 8 2 4 7))は(3 2 4)を返します。

Answer 1

filterb - filterという関数が既に存在する場合に備えて。

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

ここでは、私はそれがよりよく見えるようにすることができると確信しています。 filterと呼ばれる組込みプロシージャがすでに存在していて、それがその定義を上書きすることは良い考えではありませんので、私は、手続きmy-filterという名前

(define (my-filter pred lst) 
    (cond ((null? lst) null) 
     ((pred (first lst)) 
     (cons (first lst) (my-filter pred (rest lst)))) 
     (else (my-filter pred (rest lst))))) 

お知らせ：filter手順を記述する

Answer 2

簡単な方法。

Answer 3

は折り畳み右のインスタンスとしてfilterを定義してみてください。

(define (my-filter op xs) 
     (fold-right 
      (lambda (next result) ...) 
      '() 
      xs)) 

がヒント：フィルタの教科書定義は、他のポスターは持っている（非尾）再帰一つでありifとcons

Answer 4

を使用しますそれを理解することが重要です。あなたはライブラリ関数としてそれを書いている場合は、長いリストでスタックまたはヒープを爆破しないように、しかし、それは、末尾再帰でそれを行う方法を見つけ出すために便利です：

(define (filter pred? list) 
    (define (filter-aux result current-pair xs) 
    (cond ((null? xs) 
      result) 
      ((pred? (car xs)) 
      (set-cdr! current-pair 
        (cons (car xs) 
          '())) 
      (filter-aux result 
         (cdr current-pair) 
         (cdr xs))) 
      (else 
      (filter-aux result 
         current-pair 
         (cdr xs))))) 
    (let ((init (cons 'throw-me-out '()))) 
    (filter-aux (cdr init) init list))) 

か、let loop構文を使用：代替末尾再帰filter可変リストを必要としないために

(define (filter pred? xs) 
    (let ((result (cons 'throw-me-out '())) 
     (xs xs)) 
    (let loop ((current-pair result)) 
     (cond ((null? xs) 
      (cdr result)) 
      ((pred? (car xs)) 
      (set-cdr! current-pair 
         (cons (car xs) '())) 
      (loop (cdr current-pair) (cdr xs))) 
      (else 
      (loop current-pair (cdr xs))))))) 

Answer 5

を、あなたが使用することができ、このような何か：

(define (my-filter f lst) 
    (define (iter lst result) 
    (cond 
     ((null? lst) (reverse result)) 
     ((f (car lst)) (iter (cdr lst) 
          (cons (car lst) result))) 
     (else (iter (cdr lst) 
        result)))) 
    (iter lst '())) 

再verseはリストを2回歩く必要がありますが、不変リスト上の一定のスタックスペースを持つO（n）時間に実装できるため、全体の時間はまだO（n）です。