• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

创建Set数据类型

haskell 来源:Frank 6次浏览

所以我需要在Haskell中创建一个Set数据类型。创建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") 

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


===========解决方案如下:

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

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,intersectdifference

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

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


版权声明:本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。
喜欢 (0)