0

我已经了解了如何使用foldr和lambda查找列表中 1 的数量。但是如何使用if条件或任何其他方法来验证列表是否只有一个 1。

(define (exactlyone L)
  (foldr (lambda (elem count) (if (equal? elem 1) (+ count 1) count))
        0 L)

)

count如果可能，如何在 if 条件下使用该值？

4

3 回答 3

2

1在遍历所有列表之前，您无法确定 s 的数量，因此foldr必须消耗所有项目。之后，只需测试返回的值是否count为1：

(define (exactlyOne L)
  (= 1
     (foldr (lambda (elem count)
              (if (equal? elem 1)
                  (+ count 1)
                  count))
            0
            L)))

当然，最简单的方法是使用现有程序（例如count），而不是重新发明轮子。这将在球拍中工作：

(define (exactlyOne lst)
  (= 1
     (count (curry equal? 1) lst)))

例如：

(exactlyOne '(1 2 3))
=> #t

(exactlyOne '(1 2 3 1))
=> #f
于 2016-10-04T15:35:30.590 回答
0

如果您允许折叠的内核函数捕获包含可变变量的词法范围，则可以解决此问题。然后你可以保持累加器类型为布尔值，但有足够的状态来进行计算。

伪代码：

(foldl (let ([s 0])
        (lambda (accum item)
          ;; if (equal? item 1) and s is not already 2
          ;;   increment s
          ;; return (equal? s 1)
         )
       #f list)

您无法使用不捕获任何环境的函数来解决此问题；但为什么要限制于此？根据定义，函数是代码加上词法环境。

在上面，累加器基本上是一个假人；我们甚至不看它，因为状态s代表了我们需要的一切。我们可以使用一个布尔值s，使得状态是累加器参数和s. 我们可以在布尔累加器和布尔值之间划分状态s（以便它们一起形成代表必要的三个状态的两位计数器）。

这是一个非正式的证明，它不能在没有可变环境的情况下仅使用布尔返回函数来解决：

  1. 观察结果必须是布尔值：是否只有一个1，真或假？所以我们用作折叠内核的函数必须有一个布尔累加器，因为累加器是返回的。

  2. 折叠的累加器封装了核函数算法做出决定的整个状态。例如，如果该函数使用包含可变变量的词法范围，那将是作弊。

  3. 该算法需要累加器中的至少三个状态。累加器必须处于某个初始S0中，当看到 a 时，它从 S0 转换到S1，当看到另一个时1，它从 S2 转换到S21。然后这个累加器必须在折叠之外被解释为S0并S2表示假和S1真。

  4. 虽然理论上我们可以改变访问项目之间的累加器类型，但我们没有这方面的信息；我们不知道哪个元素是最后一个。如果我们知道我们正在查看最后一个元素，我们可以将我们的三态累加器转换为布尔值并返回它。

这就是为什么 Sylwester 的答案的第二部分使用延续：那么算法，而不是转换到S2可以直接逃出折叠并产生错误；然后累加器可以是布尔值。（一个更简单的非本地退出机制就足以代替完整的延续，例如从词法块返回）。

于 2016-10-04T19:02:50.250 回答
0

最简单的方法是进行自己的递归：

(define (only-one predicate lst)
  (let loop ((lst lst) (seen #f))
    (cond ((null? lst) seen)
          ((not (predicate (car lst))) (loop (cdr lst) seen))
          ;; from here on we know predicate is true
          (seen #f) ; at least two
          (else (loop (cdr lst) #t))))) ; recurse with seen as #t

如果你想用折叠解决它，你可以：

(define (only-one predicate lst)
  (call/cc
   (lambda (return)
     (foldl (lambda (e seen)
              (cond ((not (predicate e)) seen) ; keep seen (whatever it is)
                    (seen (return #f))         ; short circuit at second match
                    (else #t)))                ; change seen to #t
            #f
            lst))))

这用于call/cc获取退出过程，以防我们在处理所有元素之前知道结果。#f如果没有或不止一个匹配，它将是，如果只有一次，则为#t。

两者都这样工作：

(only-one (lambda (x) (equal? x 1)) '(0 1 2 3 4 5))   ; ==> #t
(only-one (lambda (x) (equal? x 1)) '(2 3 4 5))       ; ==> #f
(only-one (lambda (x) (equal? x 1)) '(0 1 2 1 3 4 5)) ; ==> #f
于 2016-10-04T16:50:31.300 回答