我正在使用a -> Bool类型的函数实现一个Set
以下是我目前为止的代码：
data Set a = S (a -> Bool)
empty :: Set a
empty = S (const False)
singleton :: Eq a => a -> Set a
singleton e = S (e ==)
belongs :: Set a -> a -> Bool
belongs (S s) = s
-- private
_combine :: (Bool -> Bool -> Bool) -> (a -> Bool) -> (a -> Bool) -> (a -> Bool)
_combine op f g = \x -> f x `op` g x
----------
union :: Set a -> Set a -> Set a
union (S s1) (S s2) = S (_combine (||) s1 s2)
intersect :: Set a -> Set a -> Set a
intersect (S s1) (S s2) = S (_combine (&&) s1 s2)
add :: Eq a => a -> Set a -> Set a
add e = union (singleton e)
remove :: Eq a => a -> Set a -> Set a
remove e = intersect (complement (singleton e))
complement :: Set a -> Set a
complement (S s) = S (not . s)
universe :: Set a
universe = S (const True)
toSet :: (a -> Bool) -> Set a
toSet = S但是我不能实现集合的基数，所以我想知道这些类型的实现是否有一个有用的用例，例如，与用列表实现的数据结构相比。
1条答案
按热度按时间wrrgggsh1#
当然，如果你对“Set”的定义仅仅意味着“一个我可以检查是否包含的东西”。将
a -> Bool视为“Set”类型意味着它只能做一件事。它当然不能有基数函数，也不能被迭代。从数学上讲，“Set”就是一个对象，它响应于element-of运算符∈。但从编程的Angular 来看，我们开始对集合有更多的期望，比如上面的操作。另一方面，正如你已经注意到的，你可以用这个集合做很多事情，如果你有两个集合，你可以取它们的交集、并集、差集和对称差集。
按照集合标准，你的类型在如何充当函子方面也有些奇怪。大多数Haskell集合都实现了
Functor，但你的永远不能。事实上，你的正好相反：Contravariant函子。因此，按照集合的标准，这是一个非常独特的数据结构，它仍然是一个有用的数据结构，但它的行为与
[]或其他在内存中存储数据的传统数据结构完全不同。