list - 方案/ Racket : A function which separates a list into two lists of elements that match a certain predicate and those that don't match it

Question

我想在 Scheme 中创建一个函数，它接受一个谓词和一个元素列表，然后输出两个单独的列表。一个包含与给定谓词匹配的原始列表元素，一个包含不匹配它的元素。

我认为我现在拥有的代码应该隔离那些与谓词匹配的代码并输出它们的列表，但代码将不起作用。

    (define tear
(lambda (pred xs)
    (cond[(null? xs) '()]
         [(list? (car xs))(cons((tear (pred (car xs)))(tear (pred (cdr xs)))))]
         [(pred (car xs))(cons((car xs)(tear (pred (cdr xs)))))]
         [else tear (pred (cdr xs))])))
(tear number? '(1 2 3 a b c))

我的编译器的结果输出是:

    tear: arity mismatch;
 the expected number of arguments does not match the given number
  expected: 2
  given: 1
  arguments...:
   #f
  context...:
   /home/jdoodle.rkt:2:4: tear
Command exited with non-zero status 1

如果您能提供任何帮助/信息，我们将不胜感激。

Answer 1

让我们逐步修复您的代码。添加缩进和空格以使其可读:

(define tear
  (lambda (pred xs)
    (cond
      [(null? xs) 
       '()]
      [(list? (car xs))
       (cons ((tear (pred (car xs))) (tear (pred (cdr xs)))))]
      [(pred (car xs))
       (cons ((car xs) (tear (pred (cdr xs)))))]
      [else 
       tear (pred (cdr xs))])))

(tear number? '(1 2 3 a b c))

我看到的第一个问题是将圆括号放在函数调用的内部(参数周围)而不是外部。您可以使用 cons 和对 tear 的递归调用来执行此操作。例如，在 tear (pred (cdr xs)) 中，您应该将第一个括号移动到函数之前。请记住，表达式中的括号几乎总是表示 (function argument ...) 形式的函数调用。

• (cons (A B)) 应该重写为 (cons A B)
• (tear (Pred Xs)) 应该重写为 (tear Pred Xs)
• tear (Pred Xs) 应该重写为 (tear Pred Xs)

通过这些修复，您的代码如下所示:

(define tear
  (lambda (pred xs)
    (cond
      [(null? xs) 
       '()]
      [(list? (car xs))
       (cons (tear pred (car xs)) (tear pred (cdr xs)))]
      [(pred (car xs))
       (cons (car xs) (tear pred (cdr xs)))]
      [else 
       (tear pred (cdr xs))])))

(tear number? '(1 2 3 a b c))
;=> (1 2 3)
(tear number? '(1 2 "not a number" 3 4))
;=> (1 2 3 4)

但是，当存在嵌套列表时，它仍然会做一些奇怪的事情:

(tear list? (list '(1 2 3) "not a list" '(4 5)))
;=error> (() ())

为了保持一致，它应该将两个列表放入一个列表中:((1 2 3) (4 5))。为此，只需删除第二个 cond 案例:

(define tear
  (lambda (pred xs)
    (cond
      [(null? xs) 
       '()]
      [(pred (car xs))
       (cons (car xs) (tear pred (cdr xs)))]
      [else 
       (tear pred (cdr xs))])))

(tear number? '(1 2 3 a b c))
;=> (1 2 3)
(tear list? (list '(1 2 3) "not a list" '(4 5)))
;=> ((1 2 3) (4 5))

它现在似乎正好完成了您想要的一半。您希望它返回两个列表:一个用于通过的元素，一个用于失败的元素。它目前只返回第一个列表。

您应该做的第一件事是记录它如何返回这两个列表。由于总是恰好有两个，因此您可以将它们作为多个值返回。

;; tear returns two values:
;;  - a list of the elements of `xs` that passed `pred`
;;  - a list of the elements of `xs` that failed `pred`

使用多个值有两个部分:返回它们和接收它们。使用 (values A B) 返回它们，使用 (let-values ([(A B) ....]) ....) 匹配结果，就像递归调用的结果。

这意味着像这样的每个递归调用 (f .... (tear ....) ....) 应该变成

(let-values ([(A B) (tear ....)])
  (values (f .... A ....)
          ???))

将其应用于您的代码:

;; tear returns two values:
;;  - a list of the elements of `xs` that passed `pred`
;;  - a list of the elements of `xs` that failed `pred`
(define tear
  (lambda (pred xs)
    (cond
      [(null? xs) 
       (values '()
               ???)]
      [(pred (car xs))
       (let-values ([(A B) (tear pred (cdr xs))])
         (values (cons (car xs) A)
                 ???))]
      [else
       (let-values ([(A B) (tear pred (cdr xs))])
         (values A
                 ???))])))

现在要填补 ??? 漏洞，请使用示例。

• (tear number? '()) 应该返回两个空列表:() ()
• (tear number? '(1 2)) 应该返回一个完整列表和一个空列表:(1 2) ()
• (tear number? '(a b)) 应该返回一个空列表和一个完整列表:() (a b)

第一个例子对应第一个???孔，第二个例子对应第二个孔，以此类推。

这告诉我们，第一个洞应该填'()，第二个洞应该填B，第三个洞应该填在 (cons (car xs) B) 中。

(define tear
  (lambda (pred xs)
    (cond
      [(null? xs) 
       (values '() '())]
      [(pred (car xs))
       (let-values ([(A B) (tear pred (cdr xs))])
         (values (cons (car xs) A)
                 B))]
      [else
       (let-values ([(A B) (tear pred (cdr xs))])
         (values A
                 (cons (car xs) B)))])))

(tear number? '(1 2 3 a b c))
;=> (1 2 3)
;   (a b c)
(tear list? (list '(1 2 3) "not a list" '(4 5)))
;=> ((1 2 3) (4 5))
;   ("not a list")