Haskell并运算封闭性判断函数测试返回False问题咨询

原因 #

你用列表（List）模拟集合，但列表是有序结构，而Haskell标准库的Data.List.union函数返回的并集结果会保留第一个输入列表的元素顺序。比如测试用例中，当计算["b", "c"]和["a"]的并集时，union返回["b","c","a"]——这个列表和你集合中的["a","b","c"]内容相同但顺序不同，elem判定它们不是同一个元素，导致函数返回False，但从集合的角度，这两个是同一个并集，你的集合其实是满足并运算封闭性的。

解决办法 #

有两种可行的修复方案：

方案1：使用真正的集合类型（推荐） #

Haskell的Data.Set模块提供了原生的无序集合实现，能正确处理集合的并集和成员判断。修改后的代码如下：

import Data.Set (Set, fromList, union, member)

closureUnderUnion :: [Set String] -> Bool
closureUnderUnion sets =
  all (\s1 -> all (\s2 -> (s1 `union` s2) `member` sets) sets) sets

测试时需要将输入的列表转换为Set：

closureUnderUnion [fromList [], fromList ["a","b","c"], fromList ["a"], fromList ["b", "c"]]

此时函数会返回True，因为Set的并集是基于内容而非顺序的，fromList ["b","c"] union fromList ["a"]等价于fromList ["a","b","c"]，而后者存在于输入集合中。

方案2：规范列表的顺序（兼容原输入类型） #

如果必须使用列表作为集合的载体，可以将所有列表转换为排序后的规范形式，这样内容相同的列表会有一致的顺序。修改代码如下：

import Data.List (sort, union)

closureUnderUnion :: [[String]] -> Bool
closureUnderUnion mp =
  let normalizedSets = map sort mp
      isUnionInSets i j = sort (union i j) `elem` normalizedSets
  in all (\i -> all (isUnionInSets i) mp) mp

此时直接传入原测试用例closureUnderUnion [[],["a","b","c"],["a"],["b", "c"]]会返回True，因为sort (union ["b","c"] ["a"])的结果是["a","b","c"]，和集合中已有的规范形式一致。

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