logo标签列表

Scheme：如何检查列表中所有元素是否相同

listlambdaschemeequality
6
我希望创建一个Scheme函数，如果传入的列表完全由相同元素组成，则返回true。这样的列表将是'(1 1 1 1)。像'(1 2 1 1)这样的列表将返回false。
以下是我目前的代码：
    (define (list-equal? lst)
      (define tmp (car lst))
      (for-each (lambda (x) 
                   (equal? x tmp))
                 lst)
      )

很明显这是不正确的，而我对此还很陌生。我猜想我无法表达我应该返回#t 或 #f的步骤。

提前感谢！

编辑： 我尝试了一下，找到了一个解决方案，似乎非常有效，并且代码很少：

(define (list-equal? lst)
 (andmap (lambda (x) 
        (equal? x (car lst)))
      lst))

再次感谢大家的帮助。

10个回答
3

如果你不关心代码只适用于数字，那么最小化代码量：

(define (list-equel? lst)
  (apply = lst))

示例：

> (list-equel? '(1 1 2 1))
#f
> (list-equel? '(1 1 1 1))
#t
> (list-equel? '(1))
#t
绝对是最好的解决方案，我简直不敢相信我没有想到。做得好。 - JasonFruit
虽然您甚至不需要长度条件。 (equal?) 没有参数 => #t。 - JasonFruit
有趣。当我测试这个想法时，我下意识地将其更正为“equal?”。我想我会为@aaz修复它。 - JasonFruit
@JasonFruit：在标准Scheme中，equal?不像=那样是可变参数的。 :-)（例如我用Racket测试过：“equal？：期望2个参数，给出3个：1 2 3”）你只能使用折叠，抱歉。 :-P - C. K. Young
@Chris Jester-Young --- 啊，我被 Guile 1.8 误导了。我会回复一条评论。 - JasonFruit
2
< p > andmap 的解决方案不错，但如果没有andmap，您可以使用此方法。它使用基本操作（and、or、null检查、等于检查）并处理空列表和一个元素列表。与Sean的实现类似，但不需要帮助定义。

(define (list-equal? args)
  (or (or (null? args)
          (null? (cdr args)))
      (and (eq? (car args) (cadr args))
           (list-equal? (cdr args)))))
(or 1 2 3) 也是合法的。 - Will Ness
0
一个简短、简洁的解决方案：
#lang racket
(define (all-equal? lst)
  (for/and
      ([i (in-permutations lst)])
    (equal? (first i) (second i))))

; TEST CASES

(require rackunit)

(check-false (all-equal? '(1 2 3)))
(check-true (all-equal? '(1 1 1)))
(check-true (all-equal? '()))

请注意，这个使用的是Racket，所以可能不适用于您的Scheme实现。
0
(define (list-equal? lst)
    (if (= (cdr lst) null)
        true
        (and (equal? (car lst) (cadr lst))
             (list-equal? (cdr lst)))))
这个似乎也不起作用，我想它到了最后会抱怨无法在一个单独的元素上使用cadr。如果我使用Racket/Pretty Big可能有所不同。 - Joseph
这将在只有一个元素的列表上引发错误。编辑：Joseph是正确的，当你到达列表末尾时，它将在任何列表上引发错误。 - Sean Devlin
@joseph：你说得对。我刚刚做的小改动应该可以解决它。 - Daniel
当您尝试获取空列表的cdr时，这仍然会出错。对于您的实现，您应该首先检查lst不是null，然后再检查(cdr lst)不是null。 - Sean Devlin
0

可以尝试这样做：

(define (list-equal? lst)
 (define (helper el lst)
  (or (null? lst)
      (and (eq? el (car lst))
           (helper (car lst) (cdr lst)))))
 (or (null? lst)
     (helper (car lst) (cdr lst))))

这可能不是最干净的实现方式，但我认为它将正确处理空列表和一个元素的列表情况。

这个很好用。非常感谢，我想我已经掌握了这个。 - Joseph
0

像这样应该可以工作：

(define (list-equal? lst)
  (cond ((< (length lst) 2) #t)
        (#t (and (equal? (car lst) (cadr lst))
             (list-equal? (cdr lst))))))
这个代码很不错，但它的时间复杂度为O(n*n)，而不是O(n) （因为对于列表中的每一个位置，都要计算其余部分的长度）。如果将基本情况调整为(or (null? lst) (null? (cdr lst)))，它将拥有更好的运行时间，并且更加简洁。 - Joshua Taylor
0

这个帖子中的其他答案似乎都太复杂了（我都看过了），所以这是我的看法：

(define (all-equal? lst)
  (define item (car lst))
  (let next ((lst (cdr lst)))
    (cond ((null? lst) #t)
          ((equal? item (car lst)) (next (cdr lst)))
          (else #f))))

根据设计，它不能与空列表一起使用。如果需要，可以轻松添加(if (null? lst) #t ...)。

0
在R6RS中有一个名为for-all的函数，它接受一个断言和一个列表作为参数，如果该断言对于列表中所有元素都返回true，则返回#t，否则返回#f，这恰好是你所需要的。
因此，如果你正在使用R6RS（或任何其他具有for-all函数的Scheme方言），你只需将代码中的for-each替换为for-all即可。
很遗憾，对我来说for-all不可用。但是知道我走在正确的轨道上还是很好的。 - Joseph
这个方法是可行的，但需要添加一步，即仍需检查lst不为空。 - Sean Devlin
@Sean：是的，很好的观点。或者干脆摆脱tmp变量，在谓词中每次调用(car lst)（对于空列表永远不会调用谓词，避免了问题）。 - sepp2k
0

另一种解决方案：

(define (all-same ls)
    (cond
     ((or (null? ls)
          (null? (cdr ls))) #t)
     (else (and (equal? (car ls) (next ls))
                (all-same (cdr ls)))))))

(define (next ls)
    (cond
     ((or (null? ls)
          (null? (cdr ls))) '())
     (else (cadr ls)))))
-1

在这些语言中，for循环不好用。建议尝试使用其他方法。

(define list-equal?
 (lambda (lst)
   (if (= lst null)
   (true)
   (foldr = (car lst) (cdr lst))
)))
那样做行不通。你正在比较列表的一个元素和布尔结果。 - Daniel
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接