如何在列表中搜索谓词

Question

我希望创建一个高阶函数，它以S-Expr和谓词作为参数，并返回给定的s-表达式中传递给定谓词的所有原子的列表。

例如

(fetch number? '(the (quick 6 fox 8 9) slick 2)) 

方案将返回(6 8 9 2)

希望有人能指点我，在家里自己学习。

我开始做的事

(define (fetch pred? ls)
    (cond
        [(null? '())]
        [(number?)]
        [(symbol?)]))

Answer 1

我们可以使用模板来构建一个解决方案，用于迭代列表列表，并在构建结果时处理这些结果。例如，这是解决问题的一种方法：

(define (fetch pred lst)
  (cond ((null? lst) '())  ; if the list is empty, return the empty list
        ((not (pair? lst)) ; if the current element is an atom
         (if (pred lst)    ; then test it using the predicate
             (list lst)    ; if the condition holds, add the current element to result
             '()))         ; otherwise ignore the current element
        (else (append (fetch pred (car lst))     ; recursive step: traverse both the car
                      (fetch pred (cdr lst)))))) ; and the cdr part of the list

以上是从零开始编写解决方案的方法。然而，在惯用模式中，建议将问题分成更小的部分，使用现有的过程(或编写通用的、可重用的过程)，并将它们组合起来形成一个答案。例如，在球拍中我们可以这样做：

; test if an object is an atom
(define (atom? x)
  (and (not (null? x))
       (not (pair? x))))

 ; map over a list of lists    
(define (map* func lst)
  (if (atom? lst)
      (func lst)
      (map (curry map* func) lst)))

; "fetch" by first mapping and then flattening the input list
(define (fetch pred lst)
  (flatten
   (map* (lambda (x) (if (pred x) x '()))
         lst)))

或者，我们还可以按照@user448810的建议，先使用flatten，然后再使用filter。不管怎么说，结果和预期的一样：

(fetch number? '(the (quick 6 fox 8 9) slick 2))
=> '(6 8 9 2)

Answer 2

这是另一种解决这个问题的方法。它在处理对时使用累加器而不是append，以消除append重复复制列表结构的现象。

(define (flat-filter pred x)
  (let recur ((x x)
              (initial '()))
    (cond ((null? x) initial)
          ((pair? x)
           (recur (car x) (recur (cdr x) initial)))
          ((pred x) (cons x initial)) ;; the one CONS call per element added
          (else initial))))

这可能是比奥斯卡·洛佩斯( orderópez)更高级的解决方案，但它很容易将其抽象成一个折叠函数(有意选择的参数顺序是为了反映fold和fold-right的参数顺序，后者是大多数作为SRFI 1的一部分提供的方案实现的一部分)：

(define (flat-fold-right func initial x)
  (cond ((null? x) initial)
        ((pair? x)
         (flat-fold-right func (flat-fold-right func initial (cdr x)) (car x)))
        (else (func x initial)))) ;; the one call to FUNC per element of input

(define (flat-filter pred x)
  (flat-fold-right (lambda (elem res)
                     (if (pred elem)
                         (cons elem res)
                         res))
                   '() x))

奖金赠品：

(define (flat-map func x)
  (flat-fold-right (lambda (elem res)
                     (cons (func elem) res))
                   '() x))

(define (flatten x)
  (flat-fold-right cons '() x))

Answer 3

把你的问题分成两部分是最容易的。

传统上称为flatten的过程从列表中删除所有嵌套；因此，(flatten '(the (quick 6 fox 8 9) slick 2))将返回(the quick 6 fox 8 9 slick 2)。

第二个过程传统上称为filter，然后扫描flatten的输出，只返回那些传递谓词的项；因此(filter number? (flatten '(the (quick 6 fox 8 9) slick 2)))将返回(6 8 9 2)。

这意味着您可以编写(define (fetch pred? ls) (filter pred? (flatten ls)))来定义您的函数。

我让你来写flatten和filter。两者都很简单，而且在你的问题以外的其他场合都很有用。您应该在您的标准工具包中同时拥有这两种工具：我知道。