Scheme列表求和问题

Question

首先，这是一项作业，但我只是在寻找提示或如何完成此任务的伪代码。

我需要使用递归来求和列表中的所有项。但是，如果遇到列表中不是数字的元素，它需要返回空集。以下是我的尝试：

(DEFINE sum-list
  (LAMBDA (lst)
    (IF (OR (NULL? lst) (NOT (NUMBER? (CAR lst))))
      '()
      (+
        (CAR lst)
        (sum-list (CDR lst))
      )
    )
  )
)

这个失败是因为无法将空集添加到其他元素中。通常，如果不是数字，我会返回0并继续处理列表。

- rem45acp

Answer 1

我建议您使用累加器来存储总和；如果在遍历列表时发现了非数字，则可以立即返回空的列表，否则递归将继续进行，直到列表耗尽为止。

以下是示例代码（请填写空白部分！）：

(define sum-list
  (lambda (lst acc)
    (cond ((null? lst) ???)
          ((not (number? (car lst))) ???)
          (else (sum-list (cdr lst) ???)))))

(sum-list '(1 2 3 4 5) 0)
> 15

(sum-list '(1 2 x 4 5) 0)
> ()

- Óscar López

---

我喜欢这个双参数的想法，但是只用一个参数真的可以实现吗？ - rem45acp

可以这样说，我能想到的最好的方法需要两个 if 语句和一个 let。使用带有两个参数的版本（也许使用一个简单调用 (inner-function x 0) 的包装函数）可能是最好的方法。此外，如果你已经遇到了尾递归，那么带有两个参数的版本是尾递归的，而任何一个带有一个参数的版本都不会是。 - Retief

Answer 2

我会选择这个：

我会选择这个：

(define (mysum lst)
  (let loop ((lst lst) (accum 0))
    (cond
      ((empty? lst) accum)
      ((not (number? (car lst))) '())
      (else (loop (cdr lst) (+ accum (car lst)))))))

- uselpa

---

我花了很长时间才弄清楚这个是如何工作的，特别是第二行有双重lst。我只能想象出一个带有两个参数的版本。 - rem45acp

你可以将(lst lst)替换为(lst2 let)，并将下面每个出现的lst更改为lst2；这可能会使它更清晰。基本上，它创建了一个名为let（或lst2）的局部变量，该局部变量使用参数lst的值进行初始化。 - uselpa

Answer 3

您的问题是需要使用cond而不是if，因为您需要考虑三种可能的分支。第一种情况是当您遇到非数字时，第二种情况是当您遇到列表末尾时，第三种情况是当您需要递归到列表的下一个元素时。第一个问题是您将非数字情况和空列表情况合并在了一起，这两种情况需要返回不同的值。递归情况大部分正确，但您需要检查返回值，因为递归调用可能会返回一个空列表。

- Retief

---

如果我将非数字情况和空列表情况分开处理，我想返回0表示空列表，返回'()表示非数字。但是，当递归调用时，它将尝试将空列表添加到之前累积的内容中，从而产生vm异常，例如：(+ 3 '())。我想唯一的解决方法是使用两个参数。 - rem45acp

@rem45acp - 很好的发现 - 在添加当前值之前，您必须检查返回值。如果您不介意不必要地处理列表的其余部分，则可能可以将“当前处于非数字状态”情况和“递归调用返回非数字”情况结合起来。 - Retief

Answer 4

因为我不够聪明，无法在一个函数中解决这个问题，所以让我们痛苦地明确：

#lang racket

; This checks the entire list for numericness
(define is-numeric-list?
  (lambda (lst)
    (cond
      ((null? lst) true)
      ((not (number? (car lst))) false)
      (else (is-numeric-list? (cdr lst))))))

; This naively sums the list, and will fail if there are problems
(define sum-list-naive
  (lambda (lst)
    (cond
      ((null? lst) 0)
      (else (+ (car lst) (sum-list-naive (cdr lst)))))))

; This is a smarter sum-list that first checks numericness, and then
; calls the naive version.  Note that this is inefficient, because the
; entire list is traversed twice: once for the check, and a second time
; for the sum.  Oscar's accumulator version is better!
(define sum-list
  (lambda (lst)
    (cond
      ((is-numeric-list? lst) (sum-list-naive lst))
      (else '()))))

(is-numeric-list? '(1 2 3 4 5))
(is-numeric-list? '(1 2 x 4 5))

(sum-list '(1 2 3 4 5))
(sum-list '(1 2 x 4 5))

输出：

Welcome to DrRacket, version 5.2 [3m].
Language: racket; memory limit: 128 MB.
#t
#f
15
'()
> 

我猜你的作业可能需要更加学术化的内容。

- Caleb Hattingh

Answer 5

尝试编写一个“is-any-nonnumeric”函数（使用递归）；然后你只需要（或者（is-any-numeric list）（sum list））就可以愚弄别人了。

- notrick