基于函数（a→Bool）实现Set的实用场景及基数实现问题咨询

问题背景 #

我用a -> Bool类型的函数实现了Haskell集合，代码如下：

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

但我无法实现集合的基数（cardinal），想咨询这种基于函数的Set实现相比列表实现是否具备实用场景。

实用场景 #

• 处理无限集合：这是它最核心的优势。列表实现只能表示有限集合，但谓词集合可以轻松描述无限域中的子集，比如所有偶数的集合toSet even、所有大于100的整数集合toSet (>100)，这类集合根本没法用列表完整存储。
• 内存效率极高：不管集合包含多少元素（哪怕无限），它只占用一个函数的内存空间。对于那些元素数量极大但可以用简单谓词描述的集合，比如"所有能被7整除的数"，比列表存储节省无数内存。
• 快速的成员判断：成员判断belongs直接调用谓词函数，时间复杂度是O(1)，而列表实现的成员判断是O(n)，元素越多差距越明显。
• 集合操作简洁高效：并、交、补这些操作本质是谓词的逻辑组合，实现起来非常简洁，而且操作本身不依赖集合大小，执行效率稳定。比如求两个无限集合的交集，只需要把两个谓词用&&组合就行，完全不需要遍历元素。

明显局限 #

• 无法计算基数：正如你遇到的问题，除非能遍历整个类型a的所有值（但很多类型是无限的，比如Integer），否则根本没法统计元素数量。列表实现则可以直接用length获取基数。
• 无法枚举元素：你没法把谓词集合里的元素逐个列出来，除非能穷举类型a的所有可能值，这对无限类型来说不可能，对有限但极大的类型也不现实。列表实现则天然支持枚举。
• 依赖谓词的正确性：集合的行为完全依赖谓词函数的逻辑，如果谓词写错了，集合就会出错，而且很难排查——你没法通过查看元素发现问题，只能通过测试成员判断来验证。

总结 #

这种实现适合不需要枚举元素、只需要判断成员关系，且集合可能无限或极大的场景。比如在定理证明、类型检查这类领域，经常需要用谓词描述抽象的集合。而如果需要频繁枚举元素、计算大小，列表实现（或者更高效的树/哈希集合）会更合适。

内容的提问来源于stack exchange，提问作者Federico Sawady