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

Question

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

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

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

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)) 上处理 eq，等等。

有没有办法解决这个问题？

Answer 1

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 as 而不是 as!除了更明确之外，这实际上与类型类发生的事情相同。注意我们的递归调用的结构和我们的数据类型定义的结构是一样的——我们有 Bush (Bush a) 所以我们用 eqBush (eqBush eqA) 进行递归>.

在此类型上的任何其他递归定义都会发生同样的事情。这是一个有用的(真的，这只是 Bush 的 fmap):

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 上编写一些其他函数来感受一下。

这里有几个其他非常规数据类型，可以尝试编写一些代码:

• 数据树 a = 叶 a | Branch (Tree (a,a)) -- 完美的二叉树。

• 数据 FunList a b = 完成 b |更多 a (FunList a (a -> b)) - a 的列表以及一个函数，该函数恰好接受那么多 a 并返回a b(这与 Traversals 相关)。