list - 如何在scheme中制作深度过滤器

Question

我有这个方案过程，它列出了谓词为真的(嵌套)列表中的所有事物。

(define (deep-filter f lst)
 (cond
  ((null? lst) '())
  ((and (atom? lst) (f lst)) lst)
  ((atom? lst) '() )
  (else (cons (deep-filter f (car lst)) 
              (deep-filter f (cdr lst))))))

一个例子:

 (deep-filter number? '(2 (a ((c)) (1)) 6)) => (2 (() ((())) (1)) 6)

是否可以修复此过程，使其不打印空列表？

提前致谢

Answer 1

试试这个:

(define (deep-filter f lst)
  (cond
    ((null? lst) '())
    ((and (atom? lst) (f lst)) (list lst))
    ((atom? lst) '())
    (else (append (deep-filter f (car lst)) 
                  (deep-filter f (cdr lst))))))

这称为展平列表，诀窍是使用 append而不是 cons并在列表中打包单个元素( cond 中的第二种情况)。请注意，这将消除所有子列表，仅返回满足谓词的元素。

如果您需要在删除空列表后保留列表结构，请改为执行以下操作:

(define (deep-filter f lst)
  (cond ((null? lst)
         '())
        ((atom? (car lst))
         (if (f (car lst))
             (cons (car lst) (deep-filter f (cdr lst)))
             (deep-filter f (cdr lst))))
        (else
         (filter (compose not null?)
                 (cons (deep-filter f (car lst)) 
                       (deep-filter f (cdr lst)))))))

现在它将按预期工作:

(deep-filter number? '(2 (a ((c)) (b)) 6))
=> '(2 6)

(deep-filter number? '(2 (a ((c)) (1)) 6))
=>'(2 ((1)) 6)

(deep-filter number? '(2 (a ((4)) (1)) 6))
=> '(2 (((4)) (1)) 6)

(deep-filter number? '(2 (a ((4)) (1)) 6 ((((((b))))))))
=> '(2 (((4)) (1)) 6)