创建Set数据类型

所以我需要在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和插入。

回答:

要建立在什么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整个的一点是要传递fx只有f x返回。

以上是 创建Set数据类型 的全部内容, 来源链接: utcz.com/qa/259119.html

回到顶部