7

出于教育目的，我在 Haskell 中玩树木。我有Tree a这样定义的类型

data Tree a = EmptyTree | Node a (Tree a) (Tree a)

以及许多共享基本约束的函数Ord a--因此它们具有以下类型

treeInsert :: Ord a => a -> Tree a -> Tree a
treeMake :: Ord a => [a] -> Tree a

等等。我也可以Tree a这样定义

data Ord a => Tree a = EmptyTree | Node a (Tree a) (Tree a)

但我不能简化我的功能并省略额外Ord a的如下：

treeInsert :: a -> Tree a -> Tree a
treeMake :: [a] -> Tree a

为什么 Haskell（与 一起运行-XDatatypeContexts）不会自动推断出这个约束？对我来说，这似乎很明显。为什么我错了？

这是一些示例源代码

data (Eq a, Ord a) => Tree a = EmptyTree | Node a (Tree a) (Tree a)

treeInsert :: a -> Tree a -> Tree a
treeInsert a EmptyTree = Node a EmptyTree EmptyTree
treeInsert a node@(Node v left right)
 | a == v = node
 | a > v = Node v left (treeInsert a right)
 | a < v = Node v (treeInsert a left) right

mkTree :: [a] -> Tree a
mkTree [] = EmptyTree
mkTree (x:xs) = treeInsert x (mkTree xs)

我得到这个

Tree.hs:5:26:
    No instance for (Ord a)
      arising from a use of `Node'
    In the expression: Node a EmptyTree EmptyTree
    In an equation for `treeInsert':
        treeInsert a EmptyTree = Node a EmptyTree EmptyTree
Failed, modules loaded: none.
4

3 回答 3

8

这是一个众所周知的关于数据声明上下文的问题。如果你定义data Ord a => Tree a = ...它所做的就是强制任何提到Tree a的函数都有一个Ord a上下文。这不会为您节省任何打字，但从好的方面来说，明确的上下文清楚地说明了需要什么。

GADT 来救援！

解决方法是使用通用抽象数据类型( GADTs)。

{-# Language GADTs, GADTSyntax #-}

我们可以通过提供显式类型签名将上下文直接放在构造函数上：

data Tree a where
   EmptyTree :: (Ord a,Eq a) => Tree a
   Node :: (Ord a,Eq a) => a -> Tree a -> Tree a -> Tree a

然后每当我们进行模式匹配时，Node a left right我们都会得到一个隐式(Ord a,Eq a)上下文，就像你想要的那样，所以我们可以开始这样定义treeInsert：

treeInsert :: a -> Tree a -> Tree a
treeInsert a EmptyTree = Node a EmptyTree EmptyTree
treeInsert a (Node top left right) 
          | a < top   = Node top (treeInsert a left) right
          | otherwise = Node top left (treeInsert a right)

派生东西

如果你只是在deriving Show那里添加，你会得到一个错误：

Can't make a derived instance of `Show (Tree a)':
  Constructor `EmptyTree' must have a Haskell-98 type
  Constructor `Node' must have a Haskell-98 type
  Possible fix: use a standalone deriving declaration instead
In the data type declaration for `Tree'

这很痛苦，但就像它说的那样，如果我们添加StandaloneDeriving扩展名 ( {-# Language GADTs, GADTSyntax, StandaloneDeriving #-})，我们就可以做类似的事情

deriving instance Show a => Show (Tree a)
deriving instance Eq (Tree a) -- wow

一切正常。哇是因为隐式Eq a上下文意味着我们不需要Eq a在实例上显式。

上下文仅来自构造函数

请记住，您只能通过使用其中一个构造函数来获取隐式上下文。（请记住，这是定义上下文的地方。）

这实际上就是为什么我们需要EmptyTree构造函数的上下文。如果我们只是把EmptyTree::Tree a, 行

treeInsert a EmptyTree = Node a EmptyTree EmptyTree

等式左侧没有(Ord a,Eq a)上下文，因此右侧的实例将丢失，Node构造函数需要它们。这将是一个错误，因此在这种情况下保持上下文一致很有帮助。

这也意味着你不能拥有

treeMake :: [a] -> Tree a

treeMake xs = foldr treeInsert EmptyTree xs

你会得到一个no instance for (Ord a)错误，因为左侧没有构造函数来给你(Ord a,Eq a)上下文。

这意味着你仍然需要

treeMake :: Ord a => [a] -> Tree a

抱歉，这次没有办法绕过它，但从好的方面来说，这很可能是您想要编写的唯一一个没有树参数的树函数。大多数树函数将在定义的左侧取一棵树并对其进行处理，因此大多数时候您将拥有隐式上下文。

于 2013-06-04T22:04:50.640 回答
2

kirelagin 关于DatatypeContexts无用是正确的。您仍然必须在所有函数中编写类约束。但是，如果您周围有很多课程，那么这里有一个小技巧，这可以让您只上一堂课。

{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE UndecidableInstances #-}

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving Show

class (Eq a, Ord a) => Foo a where

instance (Eq a, Ord a) => Foo a where

treeInsert :: Foo a => a -> Tree a -> Tree a
treeInsert a EmptyTree = Node a EmptyTree EmptyTree
treeInsert a node@(Node v left right)
 | a == v = node
 | a > v = Node v left (treeInsert a right)
 | a < v = Node v (treeInsert a left) right

mkTree :: Foo a => [a] -> Tree a
mkTree [] = EmptyTree
mkTree (x:xs) = treeInsert x (mkTree xs)

现在Foo上课就像Eq && Ord。使用类似的示例，您可以在所有函数中只用一个类替换所有类。正如@luqui 所指出的，您也可以使用ConstraintKinds它来使其工作。

或者您可以使用我认为允许您在数据定义中提及类约束的 GADT。

于 2013-06-04T21:51:18.593 回答
0

好吧，问题是这个约束适用于构造函数，而不是整个数据类型。这就是为什么DatatypeContexts它们实际上几乎没用......你可以在这里阅读更多关于它的信息。

如果您希望第二段包含解决方案，那么不幸的是，您不走运。我不知道这样的解决方案，而且它似乎确实不存在。wiki 文章提到了的用法MultiParamTypeClasses，但老实说，这并不方便。

于 2013-06-04T21:34:27.613 回答