给定Haskell函数：
head . filter fst
现在的问题是如何手动查找类型。如果我让 Haskell 告诉我类型，我会得到：
现在问题是手动如何找到类型。如果我让 Haskell 告诉我类型，那么我会得到：
head . filter fst :: [(Bool, b)] -> (Bool, b)
但我希望仅通过所定义的使用函数的签名来理解它是如何工作的，这些函数的签名如下：
head :: [a] -> a
(.) :: (b -> c) -> (a -> b) -> a -> c
filter :: (a -> Bool) -> [a] -> [a]
fst :: (a, b) -> a
编辑：有很多非常好的解释……选择最佳解释并不容易！
类型是通过一般称为统一的过程推断出来的。 Haskell属于Hindley-Milner家族，它使用这种统一算法来确定表达式的类型。
如果统一失败，则表达式就是一个类型错误。
该表达式
head . filter fst
测试通过。让我们手动进行统一，看看为什么会得到我们所得到的结果。
让我们从 filter fst 开始：
filter :: (a -> Bool) -> [a] -> [a]
fst :: (a' , b') -> a' -- using a', b' to prevent confusion
filter接受一个类型为 (a -> Bool) 的函数，然后再接收一个类型为[a]的列表作为输入，并返回一个类型也为[a]的列表。在表达式filter fst中，我们将类型为(a'，b') -> a'的参数fst传递给了filter。
为使这个表达式有效，fst的类型必须与filter的第一个参数的类型相一致。(a -> Bool) UNIFY? ((a', b') -> a')
该算法将两个类型表达式统一并尝试将尽可能多的类型变量（例如a或a'）绑定到实际类型（例如Bool）。
只有这样，filter fst才会导致一个有效的类型化表达式：
filter fst :: [a] -> [a]
a' 明显是 Bool 类型，所以类型变量 a' 解析为 Bool。
并且 (a'，b') 可以统一为 a。 所以如果 a 是 (a'，b')，而 a' 是 Bool，
那么 a 只是 (Bool，b')。filter 传递不兼容的参数，比如 42（一个 Num），
则 Num a => a 和 a -> Bool 的统一将失败，因为这两个表达式永远无法统一为正确的类型表达式。filter fst :: [a] -> [a]
这是我们正在讨论的同一个a，因此我们替换它的位置为前面统一的结果：
filter fst :: [(Bool, b')] -> [(Bool, b')]
head . (filter fst)
可以写成
(.) head (filter fst)
所以取 (.)
(.) :: (b -> c) -> (a -> b) -> a -> c
为了让unification成功，
head :: [a] -> a 必须与 (b -> c) 统一filter fst :: [(Bool, b')] -> [(Bool, b')] 必须与 (a -> b) 统一由于(2)，我们得到在表达式 (.) :: (b -> c) -> (a -> b) -> a -> c 中，a 等同于 b。
因此，在表达式 (.) head (filter fst) :: a -> c 中，类型变量 a 和 c 的值很容易确定，因为(1)给出了b和c之间的关系：即b是c的列表。由于我们知道a为[(Bool, b')]，因此c只能与(Bool, b')相统一。
因此，head . filter fst被成功地类型检查：
head . filter fst :: [(Bool, b')] -> (Bool, b')
更新
有趣的是，你可以从不同的起点统一开始这个过程。我首先选择了filter fst，然后继续使用(.)和head，但正如其他示例所展示的那样，统一可以以几种方式进行，类似于数学证明或定理推导可以用多种方式完成的方式！
filter :: (a -> Bool) -> [a] -> [a]函数接收一个函数 (a -> Bool)和一个类型相同的列表a，并返回一个同样类型的列表a。
在你的定义中，你使用了fst :: (a,b) -> a，这时候可以通过filter fst来筛选列表。
filter (fst :: (Bool,b) -> Bool) :: [(Bool,b)] -> [(Bool,b)]
推导出了结果。接下来，你将会把你的结果 [(Bool,b)] 与 head :: [a] -> a 组合起来。
(.) :: (b -> c) -> (a -> b) -> a -> c 是两个函数的组合，其中，func2 :: (b -> c) 和 func1 :: (a -> b)。在你的情况下，你有
func2 = head :: [ a ] -> a
和
func1 = filter fst :: [(Bool,b)] -> [(Bool,b)]
所以这里的head接受[(Bool,b)]作为参数，并根据定义返回(Bool,b)。最终结果如下：
head . filter fst :: [(Bool,b)] -> (Bool,b)
让我们从(.)开始。它的类型签名为
(.) :: (b -> c) -> (a -> b) -> a -> c
这段话说的是：“给定一个从 b 到 c 的函数，以及从 a 到 b 的函数，
还有一个 a，我可以给你一个 b。” 我们想要将它与 head 和 filter fst 结合使用，因此：
(.) :: (b -> c) -> (a -> b) -> a -> c
^^^^^^^^ ^^^^^^^^
head filter fst
head的函数，它是从某些东西的数组到单个东西的函数。所以现在我们知道b将会是一个数组，而c将会是该数组的一个元素。因此，对于我们表达式的目的，我们可以认为(.)具有以下签名：(.) :: ([d] -> d) -> (a -> [d]) -> a -> d -- Equation (1)
^^^^^^^^^^
filter fst
filter 的签名为：
filter :: (e -> Bool) -> [e] -> [e] -- Equation (2)
^^^^^^^^^^^
fst
请注意，我已更改类型变量的名称以避免与我们已有的as混淆！这意味着“给定一个从e到布尔值的函数和一个e列表，我可以给你一个e列表”。函数fst的签名为：
fst :: (f, g) -> f
说到一个包含f 和g的一对，我可以给你一个f。
与方程式2进行比较，我们知道e将成为一组值，其中第一个元素必须是Bool。因此，在我们的表达式中，我们可以将filter视为具有以下签名：
filter :: ((Bool, g) -> Bool) -> [(Bool, g)] -> [(Bool, g)]
我所做的只是将方程式2中的e替换为(Bool, g)。
而表达式filter fst的类型为：
filter fst :: [(Bool, g)] -> [(Bool, g)]
(a -> [d]) 现在必须是 [(Bool, g)] -> [(Bool, g)]，因此 a 必须是 [(Bool, g)]，d 必须是 (Bool, g)。因此，在我们的表达式中，我们可以将 (.) 视为具有以下签名：(.) :: ([(Bool, g)] -> (Bool, g)) -> ([(Bool, g)] -> [(Bool, g)]) -> [(Bool, g)] -> (Bool, g)
(.) :: ([(Bool, g)] -> (Bool, g)) -> ([(Bool, g)] -> [(Bool, g)]) -> [(Bool, g)] -> (Bool, g)
^^^^^^^^^^^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
head filter fst
head :: [(Bool, g)] -> (Bool, g)
filter fst :: [(Bool, g)] -> [(Bool, g)]
将所有内容整合在一起：
head . filter fst :: [(Bool, g)] -> (Bool, g)
这与您先前的代码等效，只是我使用了类型变量g而不是b。
这听起来可能很复杂，因为我详细描述了它。然而，这种推理很快就变成了第二天性，您可以在脑海中完成。
（跳过手动推导部分）
给定 head . filter fst 的类型为 ((.) head) (filter fst)
head :: [a] -> a
(.) :: (b -> c) -> ((a -> b) -> (a -> c))
filter :: (a -> Bool) -> ([a] -> [a])
fst :: (a, b) -> a
type(head, arrow(list(A) , A)). %% -- known facts
type(compose, arrow(arrow(B, C) , arrow(arrow(A, B), arrow(A, C)))).
type(filter, arrow(arrow(A, bool), arrow(list(A) , list(A)))).
type(fst, arrow(pair(A, B) , A)).
type([F, X], T):- type(F, arrow(A, T)), type(X, A). %% -- application rule
3 ?- type([[compose, head], [filter, fst]], T).
T = arrow(list(pair(bool, A)), pair(bool, A)) %% -- [(Bool,a)] -> (Bool,a)
类型被表示为复合数据项，以纯语法方式。例如，类型[a] -> a由arrow(list(A), A)表示，可能的Haskell等价物为Arrow (List (Logvar "a")) (Logvar "a")，给定适当的data定义。
只使用了一个推理规则，即应用，以及Prolog的结构统一，其中复合术语匹配，如果它们具有相同的形状和它们的组成部分匹配：f(a1, a2, ... an)和g(b1, b2, ... bm)匹配，如果f与g相同，n == m且ai匹配bi，逻辑变量能够根据需要采取任何值，但只能一次（不能更改）。
4 ?- type([compose, head], T1). %% -- (.) head :: (a -> [b]) -> (a -> b)
T1 = arrow(arrow(A, list(B)), arrow(A, B))
5 ?- type([filter, fst], T2). %% -- filter fst :: [(Bool,a)] -> [(Bool,a)]
T2 = arrow(list(pair(bool, A)), list(pair(bool, A)))
要手动进行类型推断，需要机械地将事物写在下面，侧边记录等价关系并执行替换，从而模拟Prolog的操作。我们可以将任何->，(_,_), []等仅视为语法标记，而不理解其含义，并使用结构统一来机械地执行此过程，这里只使用一条类型推断规则，即应��规则：(a -> b) c ⊢ b {a ~ c}（在a和c等价的情况下，用b替换(a -> b)和c的并置）。重命名逻辑变量以避免名称冲突非常重要。
(.) :: (b -> c ) -> ((a -> b ) -> (a -> c )) b ~ [a1],
head :: [a1] -> a1 c ~ a1
(.) head :: (a ->[a1]) -> (a -> c )
(a ->[c] ) -> (a -> c )
---------------------------------------------------------
filter :: ( a -> Bool) -> ([a] -> [a]) a ~ (a1,b),
fst :: (a1, b) -> a1 Bool ~ a1
filter fst :: [(a1,b)] -> [(a1,b)]
[(Bool,b)] -> [(Bool,b)]
---------------------------------------------------------
(.) head :: ( a -> [ c ]) -> (a -> c) a ~ [(Bool,b)]
filter fst :: [(Bool,b)] -> [(Bool,b)] c ~ (Bool,b)
((.) head) (filter fst) :: a -> c
[(Bool,b)] -> (Bool,b)
filter需要一个函数和一个列表，并返回一个列表。 filter fst指定了一个函数，但没有给出列表 - 所以我们还在等待列表输入。因此，filter fst正在获取一个列表并返回另一个列表。（顺便说一下，这是一个相当常见的Haskell短语。）.运算符将输出“管道”到head中，它期望一个列表并返回该列表中的一个元素。（恰好是第一个元素。）因此，无论filter得出什么结果，head都会给出它的第一个元素。此时，我们可以得出结论。head . filter foobar :: [x] -> x
x？ 好的，filter fst将fst应用于列表的每个元素（以决定是否保留它或抛弃它）。 因此，fst必须适用于列表元素。 而fst期望一个2元组，并返回该元组的第一个元素。 现在filter期望fst返回一个Bool，这意味着元组的第一个元素必须是Bool。head . filter fst :: [(Bool, y)] -> (Bool, y)
什么是y？我们不知道，其实也不重要！以上函数无论y是什么都能正常工作。因此这就是我们的类型签名。
在更复杂的示例中，弄清楚发生了什么可能会更难。（特别是涉及到奇怪的类实例时！）但是对于像这样涉及常见函数的小例子，您通常只需考虑“嗯，这里放入什么？那里输出什么？这个函数需要什么？”并且可以轻松找到答案，而无需进行大量手动算法追踪。
42作为参数传递给filter，则一致性将成功，并导致文字42具有类型forall a. Num(a->Bool) :: a->Bool。在处理过程的更晚阶段，ghc将报告范围内没有有效的“instance Num（a->Bool）”。这具有实际后果，因为此类错误在实践中有些常见，并且了解为什么ghc会产生此错误而不是更有用的错误提示是很有用的。 - John L