出于教育目的，我在 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. 

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

GADT 来救援！

解决方法是使用广义抽象数据类型 https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/glasgow_exts.html#generalised-algebraic-data-types-gadts (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) context.

这意味着你还需要

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

抱歉，这次没有办法解决这个问题，但从好的方面来说，这很可能是您想要编写的唯一一个不带树参数的树函数。Most树函数将在定义的左侧获取一棵树并对其执行某些操作，因此大多数时候您都会拥有隐式上下文。