Haskell - 用二叉树实现的集合笛卡尔积函数

Question

我已经在Haskell中将一个集合实现为二叉树，如下所示：

data Set a = Node | Tree a (Set a) (Set a)

我正在尝试定义一个函数，以找到两个集合的笛卡尔积，如下所示：

cartesian :: Set a -> Set b -> Set (a, b)
cartesian as bs = fromList [(a,b) | a <- (toList as), b <- (toList bs)]

我似乎无法看出这段代码的错误，希望能得到帮助和修复。

错误消息是：

error:
    • No instance for (Ord a) arising from a use of ‘fromList’
      Possible fix:
        add (Ord a) to the context of
          the type signature for:
            cartesian :: forall a b. Set a -> Set b -> Set (a, b)
    • In the expression:
        fromList [(a, b) | a <- (toList as), b <- (toList bs)]
      In an equation for ‘cartesian’:
          cartesian as bs
            = fromList [(a, b) | a <- (toList as), b <- (toList bs)]

- hafhut

---

编辑必须不影响现有答案，因此我回滚了您的编辑。谢谢。 - Will Ness

Answer 1

正如错误信息所述，您的fromList函数有一个Ord a类型约束：

fromList :: <b>Ord a =></b> [a] -> Set a
fromList = foldr insert Node

那意味着为了使用fromList函数，a应该是Ord类型类的成员。但这不在您的cartesian函数的签名中。

就像错误所说的那样，您可以将该类型限制添加到您的cartesian函数中：

cartesian :: <b>(Ord a, Ord b) =></b> Set a -> Set b -> Set (a, b)
cartesian as bs = fromList [(a,b) | a <- toList as, b <- toList bs]

Ord a, Ord b类型约束源于这样一个事实，即如果两个元素都是Ord的元素实例，则2元组是Ord的实例。实际上，该实例被定义为：

instance <b>(Ord a, Ord b) =></b> Ord (a, b) where
    -- …

- Willem Van Onsem

Answer 2

你的fromList函数假设它接收到的是一个可能包含重复项的未排序列表，所以它需要一个Ord约束来确定元素放在哪里，并清除重复项。然而，在这种情况下，你得到的是两个始终已排序且不包含重复项的列表，并将它们的笛卡尔积取出，结果列表也将始终已排序且不包含重复项。你应该创建一个新函数来实现这个目的，而不是使用fromList将这个新列表转换为集合，就像真正的Set中的fromDistinctAscList一样。要构建它，请展开foldr insert Node（我可以向你展示如何做，但你没有发布你的insert函数，所以我无法做到），并替换所有比较操作为基于它们所在位置的硬编码结果。然后，只需将其用于fromList的位置即可。这还会带来性能上的好处，因为它节省了所有冗余比较的时间。

编辑：你的insert函数完全不关心维护二叉树的任何平衡性，因此在有序列表上调用它将产生一个最大程度不平衡的树。如果你不关心这个问题，那么你可以这样实现fromDistinctAscList:

insertLeast :: a -> Set a -> Set a
insertLeast x Leaf = singleton x
insertLeast x (Tree a left right) = Tree a (insertLeast x left) right

fromDistinctAscList :: [a] -> Set a -> Set a
fromDistinctAscList = foldr insertLeast Leaf

当没有重复项且元素按升序排列时，其行为与insert和fromList完全相同。然而，它有一个不幸的后果，即它是一个严格的foldr，这是不好的。我们可以像这样进行优化:

fromDistinctAscList :: [a] -> Set a -> Set a
fromDistinctAscList = foldr (`Tree` Leaf) Leaf

虽然如此，它仍将保持最大的不平衡状态，但现在是朝另一个方向。

你还可以使常规的insert函数更加懒惰:

insert :: Ord a => a -> Set a -> Set a
insert x xs = uncurry (Tree x) $ case xs of
  Node -> (Node, Node)
  Tree a left right -> case a `compare` x of
    LT -> (insert a left, right)
    EQ -> (left, right)
    GT -> (left, insert a right)

- Joseph Sible-Reinstate Monica