我已经找到了如何使用foldr
和lambda
找到列表中的1点的数量。但如何使用if
状况或任何其他的方法来验证,如果列表中只有一个1用球拍在列表中搜索只有一个“1”
(define (exactlyone L)
(foldr (lambda (elem count) (if (equal? elem 1) (+ count 1) count))
0 L)
)
中如果有可能的,如果条件如何使用count
价值?
我已经找到了如何使用foldr
和lambda
找到列表中的1点的数量。但如何使用if
状况或任何其他的方法来验证,如果列表中只有一个1用球拍在列表中搜索只有一个“1”
(define (exactlyone L)
(foldr (lambda (elem count) (if (equal? elem 1) (+ count 1) count))
0 L)
)
中如果有可能的,如果条件如何使用count
价值?
在遍历所有列表之前,您无法确定1
的编号,因此必须使用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
最简单的方法是做你自己的递归:
(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
这个问题可以,如果你允许折叠的内核函数可以捕获包含可变变量的词法范围内解决。然后,您可以保留累加器类型布尔值,并且具有足够的状态来进行计算。
伪代码:
(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
,使得状态是累加器PARAM的组合和s
的信息。我们可以把一个布尔累加器和一个布尔s
之间的状态(让他们一起组成一个代表所需的三种状态的二位计数器)。
这是一个非正式的证据证明它不能只是一个布尔返回函数没有变化无常的环境解决:
观察,其结果必须是布尔:是,这正是一个1
,对或错?所以我们用作fold内核的函数必须有一个布尔累加器,因为累加器就是返回的。
折叠的累加器封装了内核函数的算法作出决定的整个状态。例如,如果函数使用包含可变变量的词法作用域,那就是作弊。
该算法在累加器中需要至少三个状态。累加器必须在一些初始S0,从它转换到S1当1
所看到的,从它当另一个1
看出过渡到S2。这个累加器必须在折叠之外解释为S0
和S2
表示错误,并且S1
为真。
尽管我们可以在理论上改变访问项目之间的累加器类型,但我们没有这方面的信息;我们不知道哪个元素是最后一个。如果我们知道我们正在查看最后一个元素,那么可以将我们的三态累加器忽略为一个布尔值并返回该值。
这就是为什么Sylwester的答案的第二部分使用延续:则算法,而不是过渡到S2可以逃脱出来直接折并产生虚假;累加器可以是布尔值。 (一个非常简单的非本地退出机制就足以代替全部的延续,比如从一个词块返回)。