为什么Haskell的Data.Set不支持无限集？ [英] Why doesn't Haskell's Data.Set support infinite sets?

问题描述

在下面的代码片段中：

 将限定的数据集合导入为集合
 
数据Nat =零| Succ Nat派生（Eq，Show，Ord）
 
实例Enum Nat其中
 pred（Succ x）= x 
 succ x = Succ x 
 toEnum 0 = Zero 
 toEnum x = Succ（toEnum（x-1））
 fromEnum Zero = 0 
 fromEnum（Succ x）= 1 +（fromEnum x）
 
 nats： ：[Nat] 
 nats = [零..] 
 
 natSet :: Set.Set Nat 
 natSet = Set.fromList nats 
  

为什么：

• elem（toEnum 100）nats == True

<但是

• Set.member（toEnum 100）natSet 永不结束？

解决方案

现有的答案已足够，但我想阐述一些行为 Set s。

看起来您希望所有的 Nat S;你把所有的 Nat s的无限列表，并使用 Set.toList 。那样就好了;数学家经常谈论所有自然数的集合。问题在于 Set 的实现并不像列表那样适应懒惰。



Set的实现基于大小平衡二叉树（或者b $ b树的有界余额树）。 b
$ b

Data.Set的文档

假设您希望懒惰地从列表中构造二叉树。当需要更深的树遍历时，列表中的元素只能插入树中。那么你问问100是否在树上。它会一直向树上添加数字1-99。然后它最终将100加到树上，并发现100确实是树中的一个元素。但请注意我们做了什么。我们只是执行了懒惰列表的按顺序遍历！因此，第一次，我们想象的 LazyTree.contains 与 List.find 具有大致相同的复杂性（假设一个ammortized O（1）插入，这对于一个简单的二叉树来说是一个不好的假设，它会具有 O（log n）复杂性）。如果没有平衡，我们的树会非常不平衡（我们按顺序添加了1到100的数字，所以它会成为每个分支右边的一个大链表）。但是在遍历期间树平衡时，很难知道从哪里开始遍历。至少它肯定不会马上变得直观。



tl; dr：没有人（afaik）做出了一个很好的懒惰设置。所以无限集合现在更容易表示为无限列表。

In the following snippet:

import qualified Data.Set as Set

data Nat = Zero | Succ Nat deriving (Eq, Show, Ord)

instance Enum Nat where
  pred (Succ x)     = x
  succ x            = Succ x
  toEnum 0          = Zero
  toEnum x          = Succ (toEnum (x-1))
  fromEnum Zero     = 0
  fromEnum (Succ x) = 1 + (fromEnum x)

nats :: [Nat]
nats = [Zero ..]

natSet :: Set.Set Nat
natSet = Set.fromList nats

Why does:

• elem (toEnum 100) nats == True

but

• Set.member (toEnum 100) natSet never ends?

解决方案

The existing answers are sufficient, but I want to expound a little bit on the behavior of Sets.

Looks like you are hoping for a lazy set of all Nats; you take the infinite list of all Nats and use Set.toList on it. That would be nice; mathematicians often talk in terms of the "set of all natural numbers". The problem is the implementation of Set is not as accommodating of laziness as lists are.

The implementation of Set is based on size balanced binary trees (or trees of bounded balance)

The docs for Data.Set

Suppose you wish to lazily construct a binary tree from a list. Elements from the list would only be inserted into the tree when a deeper traversal of the tree was necessary. So then you ask if 100 is in the tree. It would go along adding numbers 1-99 to the tree, one at a time. Then it would finally add 100 to the tree, and discover that 100 is indeed an element in the tree. But notice what we did. We just performed an in-order traversal of the lazy list! So the first time, our imaginary LazyTree.contains would have roughly the same complexity as List.find (assuming an ammortized O(1) insert, which is a bad assumption for a simple binary tree, which would have O(log n) complexity). And without balancing, our tree would be very lopsided (we added the numbers 1 through 100 in order, so it would just be a big linked list down the right child of each branch). But with tree balancing during the traversal, it would be hard to know where to begin the traversal again; at least it certainly wouldn't be immediately intuitive.

tl;dr: nobody (afaik) has made a good lazy Set yet. So infinite Sets are more easily represented as infinite lists, for now.

这篇关于为什么Haskell的Data.Set不支持无限集？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！