为什么我不能声明推断类型？

Question

我有以下内容:

runcount :: (Eq a, Num b) => [a] -> b
runcount = runcountacc 0

runcountacc :: (Eq a, Num b) => b -> [a] -> b
runcountacc n (_:[]) = runcountacc (n+1) []
runcountacc n (x:xs) = runcountacc (n+(if head xs==x then 0 else 1)) xs 
runcountacc n _ = n

当我尝试将其加载到Hugs时会生成此错误:

:6 - Cannot justify constraints in explicitly typed binding
*** Expression    : runcountacc
*** Type          : (Eq a, Num b) => b -> [a] -> b
*** Given context : (Eq a, Num b)
*** Constraints   : Eq c

加载到ghci时出现以下错误:

:6:23: Ambiguous type variable `a0' in the constraint:
  (Eq a0) arising from a use of `runcountacc'
Probable fix: add a type signature that fixes these type variable(s)
In the expression: runcountacc (n + 1) []
In an equation for `runcountacc':
   runcountacc n ([x]) = runcountacc (n + 1) []

但是,当runcountacc删除类型声明时:

runcount :: (Eq a, Num b) => [a] -> b
runcount = runcountacc 0

runcountacc n (_:[]) = runcountacc (n+1) []
runcountacc n (x:xs) = runcountacc (n+(if head xs==x then 0 else 1)) xs 
runcountacc n _ = n

代码加载正常,当询问ghci的类型runcountacc是什么时,我们得到以下结果:

?> :t runcountacc 
runcountacc :: (Num a, Eq a1) => a -> [a1] -> a

为什么我不能声明推断类型runcountacc？

Answer 1

为什么我不能在代码中编写推断类型的runco​​untacc？

简短的回答是,因为您错误地创建了多态递归,并且如果存在多态递归,则类型推断根本不起作用.

GHC提供了更好的错误消息:

orig.hs:5:24:
    Ambiguous type variable `a0' in the constraint:
      (Eq a0) arising from a use of `runcountacc'
    Probable fix: add a type signature that fixes these type variable(s)
    In the expression: runcountacc (n + 1) []
    In an equation for `runcountacc':
        runcountacc n (_ : []) = runcountacc (n + 1) []

在那里它无法推断出右侧的类型[].以下签名修复了问题,因为没有它,不清楚应该使用什么的空列表:

runcountacc n (_:[]) = runcountacc (n+1) ([] :: [a])

我们在这里有一种(无限的)多态递归.右侧空列表的类型可以是任何类型,GHC无法理解哪一个.例如,以下内容仍然有效:

runcountacc n (_:[]) = runcountacc (n+1) ([] :: [String])

不过类型签名问题消失的原因仍然存在.

@pigworker的想法是,如果省略签名,Haskell不允许多态递归,并且单态回归不存在歧义.

注意:你得到了递归错误的基本情况 - 首先不能出现无限循环.

Answer 2

我的猜测是,当你省略类型签名时,Haskell假设你不打算使用多态递归(对于哪种类型的推断不是那么有效).相应地,当您进行递归调用时runcountacc (n + 1) [],列表元素类型与原始函数调用中的类型相同.通常的Hindley-Milner过程工作正常,计算统一的单态类型runcountacc,然后通过推广自由类型变量和未解决的约束来形成类型方案.

但是,只要您编写类型签名,就允许多态递归的可能性,并且当您调用时runcountacc (n + 1) [],没有理由假设未确定的元素类型[]应该是特定的任何内容.但是,这个未确定类型仍然需要一个Eq实例来满足约束runcountacc,并且无法确定Eq要使用的实例.这真的很模糊.

有很多方法可以重写此代码以解决这种歧义.