继丹尼尔·瓦格纳的建议,你可以定义一组作为谓语指示元素是否在集合:
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和插入。
查找'filter'的源代码。你会发现'setSuchThat = filter'。 – Alec
这将是不可能的。有无数的可能的字符串。程序如何知道它具有所有返回“真”的值?更现实的解决方案是使用'filter'。 – 4castle
如果你唯一需要实现的功能是'setSuchThat',那么让我建议'输入Set a = a - > Bool'。你应该找到'setSuchThat'这个微不足道的东西。 –