如何理解 "f = ap min" 的类型推断？

Question

我一直在努力理解下面关于类型推断的另一个例子，

min :: Ord a => a -> a -> a
ap  :: Monad m => m (a -> b) -> m a -> m b

f   :: Ord a => (a -> a) -> a -> a
f   =  ap min

f reverse "on" -- "no"

当 ap 应用于 min 时，如何推断 f 的类型？我应该在哪里寻找有关 Haskell 中类型推断主题的一些实用参考资料？

Answer 1

你的问题与统一的概念有关，统一可以大致描述为寻找受环境约束的表达式类型的过程。看看这个由 Stephen Diehl 开发的优秀 course/manual，

http://dev.stephendiehl.com/fun/#january

第 5 至 8 章描述了您要查找的内容。

Answer 2

ap     :: Monad m => m (a -> b) -> m a -> m b
min    :: Ord a => a -> a -> a
-------------------------------------------------
ap min :: ?

既然min是ap的参数，那就意味着我们需要想办法unify这两个类型：

Monad m => m (a -> b)
Ord a => a -> a -> a

为此，首先我们需要弄清楚Monad 实例（如果有）适用于此处。由于a -> a -> a与a -> (a -> a)相同，因此m类型变量需要等同于(->) a。（请注意，Haskell 也支持类型系统中的柯里化和部分；正如 (+) 1 是函数 (+) 对参数 1、(->) a 是类型构造函数 (->) 对类型 a 的部分应用。)

所以我们重写为：

Monad m => m        (a -> b)
  Ord a => ((->) a) (a -> a)

这样可以很容易地可视化我们需要在 ap:

类型中进行的替换

m := Ord a => (->) a
a := Ord a => a
b := Ord a => a

但在我们继续之前，我们需要确定是否存在 (->) a 的 Monad 实例，否则这是一个类型错误。但以下是标准 Monad 实例之一，它可以：

instance Monad ((->) r) where
    return a = const a
    fa >>= g = \r -> g (fa r) r

所以现在让我们进行替换：

ap     :: Ord a => ((->) a) (a -> a) -> ((->) a) a -> ((->) a) a
min    :: Ord a => a -> a -> a
--------------------------------------------------------
ap min :: ?

取消 ap 中的类型：

ap     :: Ord a => (a -> a -> a) -> (a -> a) -> a -> a
min    :: Ord a => a -> a -> a
--------------------------------------------------------
ap min :: ?

现在希望很容易看到解决方案：

ap     :: Ord a => (a -> a -> a) -> (a -> a) -> a -> a
min    :: Ord a =>  a -> a -> a
--------------------------------------------------------
ap min :: Ord a => (a -> a) -> a -> a

如何理解 "f = ap min" 的类型推断？

How to understand type inference of "f = ap min"?

haskell

type-inference