Haskell中自动函数约束推论的类型约束 [英] Type constraints for automatic function constraint deduction in Haskell

问题描述

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

For educational purposes I am playing around with trees in Haskell. I have Tree a type defined like this

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

和许多具有基本约束的函数- Ord a -因此它们具有类似

and a lot of functions that share a basic constraint - Ord a - so they have types like

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

，依此类推.我也可以像这样定义 Tree a

and so on. I can also define Tree a like this

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

但是我不能简化我的功能，并省略以下额外的 Ord a :

but I can not simplify my functions and omit the extra Ord a to be as the following:

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

为什么Haskell(与 -XDatatypeContexts 一起运行)不能自动推断出此约束?对我来说似乎应该很明显.我为什么错了?

Why does Haskell (running with -XDatatypeContexts) not automatically deduce this constraint? It seems to to be quite obvious for me that it should. Why am I wrong?

这是一些示例源代码

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，则= =>.Tree a = ... 的所有作用是强制任何提及 Tree a 的函数具有 Ord a 上下文.这不会节省您任何键入的费用，但从正面看，明确的上下文可以清楚地了解所需的内容.

This is a well-known gotcha about contexts for data declaration. If you define data Ord a => Tree a = ... all it does is force any function that mentions Tree a to have an Ord a context. This doesn't save you any typing, but on the plus side an explicit context is clear about what's needed.

解决方法是使用我们可以通过提供显式类型签名将上下文直接放在构造函数上:

We can put the context on the constructor directly, by providing an explict type signature:

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

，然后每当我们与 Node左右匹配进行模式匹配时，我们都会得到一个隐式的(Ord a，Eq a)上下文，就像您想要的那样，因此我们可以开始像这样定义 treeInsert :

and then whenever we pattern match with Node a left right we get an implicit (Ord a,Eq a) context, just like you want, so we can start to define treeInsert like this:

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) 

派生东西

如果仅在其中添加 driving 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 扩展名( {-#语言GADT，GADTSyntax，StandaloneDeriving#-} )，那么我们可以像

That's a pain, but like it says, if we add the StandaloneDeriving extension ({-# Language GADTs, GADTSyntax, StandaloneDeriving #-}) we can then do stuff like

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

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

and everything works out ok. The wow was because the implicit Eq a context means we don't need an explicit Eq a on the instance.

请记住，您只能通过使用构造函数之一来获取隐式上下文.(请记住，这是定义上下文的地方.)

Bear in mind that you only get the implicit context from using one of the constructors. (Remember that's where the context was defined.)

这实际上就是为什么我们需要 EmptyTree 构造函数上的上下文的原因.如果我们只是将 EmptyTree :: Tree a 放到行中

This is actually why we needed the context on the EmptyTree constructor. If we'd just put EmptyTree::Tree a, the line

treeInsert a EmptyTree = Node a EmptyTree EmptyTree

在等式的左侧将没有(Ord a，Eq a)上下文，因此右侧将缺少这些实例，而对于 Node 构造函数.那将是一个错误，因此在这种情况下保持上下文一致很有帮助.

wouldn't have an (Ord a,Eq a) context from the left hand side of the equation, so the instances would be missing from the right hand side, where they're needed for the Node constructor. That would be an error, so it's helpful in this case to keep the contexts consistent.

这也意味着您不能拥有

treeMake :: [a] -> Tree a

treeMake xs = foldr treeInsert EmptyTree xs

您将得到一个没有针对(Ord a)错误的实例，因为左侧没有构造函数为您提供(Ord a，Eq a)上下文.

you'll get a no instance for (Ord a) error, because there's no constructor on the left hand side to give you the (Ord a,Eq a) context.

这意味着您仍然需要

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

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

There's no way round it this time, sorry, but on the plus side, this may well be the only tree function you'll want to write with no tree argument. Most tree functions will take a tree on the left hand side of the definition and do somthing to it, so you'll have the implicit context most of the time.

这篇关于Haskell中自动函数约束推论的类型约束的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！