2

我正在尝试在 frege 中实现经典的树结构，只要我不使用“派生”，它就可以很好地工作：

data Tree a = Node a (Tree a) (Tree a)
            | Empty
derive Show Tree

给我

realworld/chapter3/E_Recursive_Types.fr:7: kind error, 
type constructor `Tree` has kind *->*, expected was *

这不支持还是我必须以不同的方式声明它？

4

1 回答 1

4

欢迎来到类型种类的世界！

您必须提供要显示的项目的完整类型。Tree不是类型 (kind *)，而是需要类型参数才能成为类型 (kind ) 的东西* -> *。

尝试

derive Show (Tree a)

请注意，这是

derive Show (Show a => Tree a)

这类似于这样一个事实，要显示一棵树，您还需要知道如何显示树中的值（至少，derive 生成​​的代码需要知道这一点 - 当然，可以手动编写一个实例来打印只是树的形状，所以不需要它）。

通常，每个类型类的实例中所需的种类是固定的。错误消息告诉您需要 kind *for Show。

编辑：消除另一个可能的误解

请注意，这与您的递归类型无关。我们以可选值的定义为例：

data Maybe a = Nothing | Just a

这种类型不是递归的，但我们仍然不能说：

derive Show Maybe   -- same kind error as above!!

但是，给定以下类型类：

class ListSource c    -- things we can make a list from
    toList :: c a -> [a]

我们需要说：

instance ListSource Maybe where
    toList (Just x) = [x]
    toList Nothing  = []

（instance并且derive为了讨论而等效，两者都创建实例，不同之处在于derive为某些类型类自动生成实例函数。）

诚然，不清楚为什么在一种情况下是这样，而在另一种情况下却不同。关键是，在每种情况下，我们要使用的类操作的类型。例如，在课堂上Show我们有：

class Show s where
    show :: s -> String

现在，我们看到所谓的类类型变量s（代表任何未来实例化的类型表达式）单独出现在函数数组的左侧。当然，这表明它s必须是一个普通类型（kind *），因为我们将一个值传递给show并且每个值都有一个 kind 类型*。我们可以有类型Intor的值，但没有值有类型Maybe Intor 。Tree StringMaybeTree

另一方面，在 的定义中ListSource，类类型变量c被应用于a的类型中的一些其他类型变量toList，它也显示为列表元素类型。从后者，我们可以得出结论，它a有种类*（因为列表元素是值）。我们知道，函数箭头左边和右边的类型*也必须有 kind，因为函数接受和返回值。所以，c a 有种*。因此，c当应用于一种类型时，单独的东西会*产生一种类型*。这是写的* -> *。

这意味着，用简单的英语来说，当我们想要创建一个实例时，ListSource我们需要一些“容器”类型的类型构造函数，该类型构造函数用另一种类型参数化。在这里是可能的，但Tree不是。MaybeInt

于 2013-10-04T09:45:20.450 回答