3

我定义了一个嵌套数据类型 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) 我可以定义一个函数 eqB' over的递归调用Bush(Bush)，但我必须处理 eq on Bush(Bush(Bush))，依此类推。

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

4

2 回答 2

9

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

这种类型的任何其他递归定义都会发生同样的事情。这是一个有用的（这只是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)

这种递归称为多态递归，因为多态函数以与调用它的类型不同的类型调用自身。多态递归可能很难弄清楚——事实上，类型推断对于它是不可判定的（通常），所以你必须编写自己的类型签名（通常）——但通过一些练习，它看起来可能很多更自然。试着写一些其他Bush的函数来感受一下。

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

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

  • dataFunLista b = Done b | More a (FunList a (a -> b))-- 一个as 列表以及一个函数，该函数恰好接受那么多as 并返回 a b（这与Traversals相关）。

于 2012-12-04T12:34:04.810 回答
0

例如 Bush Int 中所有 Int 出现的总和

sum:: Bush Int -> Int
sum BEmpty = 0
sum (BCons i BEmpty) = i
sum (BCons i bbush) = i + sum' bbush

我可以编写一个函数 sum' 来处理 bbush：

sum':: Bush (Bush Int) -> Int
sum' BEmpty = 0
sum' (BCons bush bbbush) = sum bush -- + sum'' bbbush

没有结局……

于 2012-12-04T11:43:56.257 回答