Haskell 隐式参数和多态递归

Question

我有一个问题 GHC 用户指南的“Implicit parameters and polymorphic recursion”一章。

密码是

len1 :: [a] -> Int
len1 xs = let ?acc = 0 in len_acc1 xs

len_acc1 [] = ?acc
len_acc1 (_:xs) = let ?acc = ?acc + (1::Int) in len_acc1 xs

------------

len2 :: [a] -> Int
len2 xs = let ?acc = 0 in len_acc2 xs

len_acc2 :: (?acc :: Int) => [a] -> Int
len_acc2 [] = ?acc
len_acc2 (_:xs) = let ?acc = ?acc + (1::Int) in len_acc2 xs

章节说

In the former case, len_acc1 is monomorphic in its own right-hand side, so the implicit parameter ?acc is not passed to the recursive call. In the latter case, because len_acc2 has a type signature, the recursive call is made to the polymorphic version, which takes ?acc as an implicit parameter.

问题是

在这种情况下，“在它自己的右侧是单态的”是指类型 len_acc1 :: (?acc :: Int) => [a] -> p？为什么 ghci 说 len_acc1 :: (?acc::Int) => [a] -> Int?
为什么第一个函数是单态的而第二个不是？如果我的理解是正确的，则反之亦然。
或者可能表示类型是len_acc1 :: [a] -> Int，但每种情况都指的是?acc隐含值，所以我认为类型应该提到(?acc :: Int)约束。
单态性如何暗示隐式参数未传递给函数？

Answer 1

我只能回答部分问题

Why does ghci say len_acc1 :: (?acc::Int) => [a] -> Int?

是Int因为第一个子句returns?acc从第二个子句?acc + (1::Int)可以推导出Int

"in... right-hand side"

表示=之后的部分，其类型如上Int，是单态的。 len_acc1 :: (?acc :: Int) => [a] -> p 将是 poly-morphic.

Or may be it means that the type is len_acc1 :: [a] -> Int, but each case refers to ?acc implicit value, so I believe the type should mention (?acc :: Int) constraint.

这似乎是对我说的话；至少暂时它被视为具有该类型。但是后来我根本不明白为什么它会编译。

我试图阅读 the paper 隐式参数的定义，但没有找到答案。

Answer 2

在Haskell中，我们经常将带有类型变量的类型签名称为多态的，比如多态函数id，这里的类型签名包括类型变量a:

id :: a -> a

但是，这个签名是多态的，不是因为它包含类型变量 a，而是因为该变量是 量化的 。在Haskell中，类型签名是隐式通用量化的，所以上面等价于：

id :: forall a. a -> a

如果您打开 ExplicitForAll 扩展，这实际上是可接受的语法。正是这种量化使类型具有多态性。

当 Haskell 键入没有类型签名的绑定时，它使用 Hindley-Milner 键入算法来分配类型。该算法的工作原理是将单态类型签名分配给相互依赖的绑定集，然后通过确定它们之间的关系来细化它们。这些签名允许包含类型变量 (!)，但它们仍被视为单态的，因为变量未量化。也就是说，变量被想象为代表特定类型，我们只是还没有弄清楚它们，因为我们正在进行类型检查。

一旦类型检查完成，并且分配了“最终”单态类型，就会有一个单独的泛化步骤。所有保留在单态类型中的类型变量，还没有被确定为固定类型，如 Int 和 Bool，通过通用量化来概括。该步骤确定绑定的最终多态类型。约束是量化过程的一部分，因此当我们从单态类型移动到多态类型时，约束仅应用于泛化步骤中的类型签名。

文档提到的事实是，在推断 len_acc1 的类型时，算法会为其分配一个单态类型，最终是具有自由（即未量化）的最终单态类型 len_acc1 :: [a] -> Int ) 类型变量 a。虽然类型检查器会注意到需要 (?acc :: Int) 约束，但它不会使这部分成为 len_acc1 的推断类型。特别是，分配给 len_acc1 的递归调用的类型是没有约束的单态类型 [a] -> Int。只有在确定 len_acc1 的最终单态类型后，才会通过量化 a 并添加约束来概括它，以产生最终的顶级签名。

相比之下，当提供顶级多态签名时：

len_acc2 :: forall a. (?acc :: Int) => [a] -> Int

绑定 len_acc2 在其使用的任何地方都是多态的（连同其关联的约束），特别是在递归调用中。

结果是 len_acc1 被单态递归调用，没有约束字典提供（新）?acc 参数值，而 len_acc2 被多态调用，有约束字典对于新的 ?acc 值。我认为，这种情况是隐式参数所独有的。否则您不会遇到递归调用可以单态和多态键入的情况，使得代码在两种类型下的行为不同。

您更有可能运行遇到如下情况，其中需要“明显”类型签名，因为无法推断出单态类型：

data Binary a = Leaf a | Pair (Binary (a,a)) deriving (Show)

-- following type signature is required... 
-- toList :: Binary a -> [a]
toList (Leaf x) = [x]
toList (Pair b) = concatMap (\(x,y) -> [x,y]) (toList b)

main = print $ toList (Pair (Pair (Leaf ((1,2),(3,4)))))

Haskell 隐式参数和多态递归

Haskell Implicit parameters and polymorphic recursion

haskell

monomorphism