haskell - 在Haskell中对Bush数据类型定义相等运算

我定义了一个嵌套数据类型Bush:

data Bush a = BEmpty | BCons a (Bush(Bush a))

现在，我尝试在Bushs上定义一个相等函数:

eqB :: Eq a => Bush a -> Bush a -> Bool
eqB BEmpty BEmpty = True
eqB BEmpty _ = False
eqB _ BEmpty = False
eqB (BCons x bbush1) (BCons y bbush2) = x == y -- && ....

问题是对Bush(Bush)的递归调用
我可以在Bush(Bush)上定义一个函数eqB'，但是我必须在Bush(Bush(Bush))上处理eqB，依此类推。

有办法解决这个问题吗？

最佳答案

Bush是一种“非常规”或“非统一”数据类型，这意味着在递归情况下，它不使用与给定的类型参数相同的类型参数。这些有时可能很难解释，但是在这种情况下，答案比您想象的要简单:

data Bush a = BEmpty | BCons a (Bush (Bush a))

instance Eq a => Eq (Bush a) where
    BEmpty == BEmpty = True
    BCons x xs == BCons y ys = x == y && xs == ys
    _ == _ = False

而已! (==)可以递归地调用自身，我们完成了。

但是，等等，我们在这里拉了一个肮脏的把戏:我们正在使用Eq和类型类机制，这对我们来说是辛苦的工作。

如果根本没有类型类，我们该怎么办？好吧，如果我们没有类型类，那么我们就不能首先使用Eq a =>约束。相反，我们可以传递一个显式比较函数:: a -> a -> Bool。因此，考虑到这一点，我们可以编写非常相似的代码:

eqBush :: (a -> a -> Bool) -> Bush a -> Bush a -> Bool
eqBush _ BEmpty BEmpty = True
eqBush eqA (BCons x xs) (BCons y ys) = eqA x y && eqBush (eqBush eqA) xs ys
eqBush _ _ _ = False

在每个递归调用中，我们没有传递与我们得到的相同的比较函数，而是传递了一个比较函数来比较Bush a而不是a!除了更显式之外，这实际上与类型类相同。请注意，递归调用的结构与数据类型定义的结构如何相同-我们具有Bush (Bush a)，因此我们使用eqBush (eqBush eqA)进行递归。

对于此类型的任何其他递归定义，也会发生相同的情况。这是一个有用的代码(实际上只是fmap的Bush):

mapBush :: (a -> b) -> Bush a -> Bush b
mapBush _ BEmpty = BEmpty
mapBush f (BCons x xs) = BCons (f x) (mapBush (mapBush f) xs)

这样，编写像sumBush这样的函数就很容易了:

sumBush :: Bush Int -> Int
sumBush BEmpty = 0
sumBush (BCons x xs) = x + sumBush (mapBush sumBush xs)

这种递归称为polymorphic recursion，因为多态函数以与调用时不同的类型调用自身。多态递归可能很棘手-实际上，类型推断是无法确定的(通常)，因此，您必须编写自己的类型签名(通常)-但经过实践，它看起来似乎很多更自然。尝试在Bush上编写其他一些功能，以便对此有所了解。

以下是一些其他非常规数据类型，可尝试为以下代码编写一些代码:

data Tree a = Leaf a | Branch (Tree (a,a))-完美的二叉树。

data FunList a b = Done b | More a (FunList a (a -> b))-a的列表以及一个函数，该函数正好采用了那么多a并返回一个b(与Traversals有关)。