实现为二叉树的集合的Haskell - cartesian函数

Question

我在Haskell中实现了一个set作为二叉树，如下所示：

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)]

Answer 1

您的fromList函数假设它接收到一个可能包含重复项的未排序列表，因此它需要一个Ord约束来确定将元素放在哪里，并清除重复项。然而，在本例中，您将得到两个列表，这两个列表将始终排序且不包含重复项，并采用其笛卡尔乘积，结果列表也将排序且不包含重复项。就像fromDistinctAscList in the real Set一样，您应该为此创建一个新函数，而不是使用fromList将这个新列表转换为一个集合。为此，展开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)