有没有办法将列表转换为Scheme中的一个集合？

问题描述：

我想测试列表之间的平等，但我真的只关心成员是相同的，而不是排序。有没有简单的操作员来检查这个？有没有办法将列表转换为Scheme中的一个集合？

一个相当简单的例子

(my-equal? (a b) (b a))

应该返回#T。

显然，这个具体的例子可以很容易地通过检查两个列表，然后反向第二，并再次检查

(or (equal? (a b) (b a)) (equal? (a b) (reverse (b a)))

但有一般的方式呢？我可能会试图编写一个函数，但我只能想象一些相当复杂的工作。我猜这肯定是一个相当普遍的需求，我想知道方案是否有内部操作员可以在这里完成工作。

我使用MIT的方案9.0.1

一个未指定的问题是您是否会考虑像'（1 1 2）和'（2 1）这样的列表是否相等。换句话说，重复计算什么？ – john

请记住，在Scheme ...列表数据结构被写入（列表7 8）或（cons 9（cons null））。也许你应该写一个哈希映射到Set来实现。从那里你可以建立起来。 – user618677

@john如果它是一个基本集合，那么不应该重复计数。 – jones

答

如果你实现了SRFI 1可用，有lset=达到你想要的东西：

Set operations on lists

请注意，这不会“将列表转换为集合” - 它只是*将*列表视为集合。（这对于一些有限的情况很有用。） –

@Chris Jester-Young：感谢编辑！ –

优秀。谢谢。这正是我所期待的。 – jones

答

如果您使用的球拍，我会指向this page，内置支持套件。

不，这不是回答你的问题，我知道。

答

或者如果你想做老派，你可以写一些小功能。

我真诚地希望你不要用这个作业。

(define (unordered-union-set set1 set2) 
    (cond ((null? set2) set1) 
     (else 
      (if (in-set? (car set2) set1) 
       (unordered-union-set set1 (cdr set2)) 
       (cons (car set2) (unordered-union-set (cdr set2) set1)))))) 

(define (in-set? item set) 
    (cond ((null? set) #f) 
     ((equal? item (car set)) #t) 
     (else (in-set? item (cdr set))))) 

(define (set-equal? set1 set2) 
    (if (equal? (length set1) (length set2)) 
     (if (equal? (length set1) (length (unordered-union-set set1 set2))) 
      #t 
      #f) 
    #f))

使用set-equal？在任何两套。

这是基于一些简单的集合论。如果两组等价基数的联合产生一个基数等于第一个或最后一个集合的基数的集合，则这些集合是等价的。

我写这一点是说，有这个没有简单的操作，但如果你使用并集招长期复杂的过程是没有必要的。

我的实现没有SRFI 1，但我很怀疑LSET =会比这更快的功能。

但现在，我看了你的意见，你需要它的有效“（112）和”（1:2）。由于这些不是集合，这种方法将不起作用，但不难实现。所以，实际上，这个过程相当于lset =。

有没有办法将列表转换为Scheme中的一个集合？

相关推荐