创建Set数据类型

Question

所以我需要在Haskell中创建一个Set数据类型。

所以，我的问题的第一部分，我需要定义

type Set a = ... 

我把它设置为

type Set a = Set [a] 

因为套装也只是α的名单，对不对？ 或者，将正确的方式做到这一点是

type Set a = ([a]) 

然后，在接下来的一部分，我需要实现的功能

setSuchThat :: (a -> Bool) -> (Set a) 

功能需要一个特征函数f并返回一组这样仅当f（x）为真时，值x（适当类型）才在该集合中。因此，它在使用中的例子是，

setSuchThat (\x -> x == "coke") 

所以我的问题是，现在，是该函数我基本上需要评估该功能让“可乐”，然后将其添加到我的设置。我想我只是不明白，在这个功能中，我会去做这件事。

Answer 1

继丹尼尔·瓦格纳的建议，你可以定义一组作为谓语指示元素是否在集合：

type Set a = a -> Bool 

良好的措施，我将使用一个newtype，以使其更清晰这里我们使用集：

newtype Set a = Set { contains :: a -> Bool } 

然后setSuchThat只是包装一个谓语Set：

setSuchThat :: (a -> Bool) -> Set a 
setSuchThat = Set 

您可以使用contains功能的一组测试成员：

> setSuchThat (== "coke") `contains` "coke" 
True 

> setSuchThat (== "coke") `contains` "pepsi" 
False 

所以空集只是setSuchThat (const False) - 对于任何给定的元素，它总是回答这个问题：“请问一套包含此元素？“ 没有”。

insert :: (Eq a) => a -> Set a -> Set a 
insert x s = Set $ \ x' -> x == x' || s `contains` x' 

> insert "pepsi" (setSuchThat (== "coke")) `contains` "pepsi" 
True 

像union其他功能很容易：

然后你就可以实现诸如insert由组成现有contains功能与新的功能扩展集新元素

union :: Set a -> Set a -> Set a 
union s1 s2 = Set $ \ x -> s1 `contains` x || s2 `contains` x 

> let sodas = setSuchThat (== "coke") `union` setSuchThat (== "pepsi") 

> sodas `contains` "coke" 
True 

> sodas `contains` "pepsi" 
True 

> sodas `contains` "water" 
False 

作为练习，请尝试执行其他设置功能，如delete,intersect和difference。

此方法的一个缺点是每个查找都是线性-O（n） - 插入或删除元素的数量。此外，你不能简单地枚举集将其转换为A的所有元素列表中，你只能列举值和测试每一个是否是一个元素。不过，其中一个的优势就是让您轻松表示无限集;例如，setSuchThat (> 0)包含所有非负数。

这就是为什么标准Data.Set类型使用基于树的数据结构，而不是功能，代表元素，它们的实际值。用这种方法，值可在不增加集的大小被删除，并且，因为它使用Ord代替Eq，实现了更有效的对数O（log n）的-lookups和插入。

Answer 2

要建立在什么Jon Purdy打下了：

你需要考虑的Set a = a -> Bool的作为，你必须一起工作的限制。当您看到setSuchThat :: (a -> Bool) -> (Set a)时，您可以将其读取为与setSuchThat :: (Set a) -> (Set a)或setSuchThat :: (a -> Bool) -> (a -> Bool)相同。 setSuchThat有点像一个mcguffin，它只是在那里使用更清晰的功能 - 这是没有必要的。你正在做

一切都是以功能f并将其应用到变量x。的setSuchThat整个的一点是要传递f和x只有f x返回。