Haskell新手求助：推导函数f的最一般类型

已知：

• 函数定义：

  f x _ False = x
  f _ x y     = maybe 42 (g y) x
  

• g :: a -> [a] -> b

步骤1：确定第三个参数的类型 #

第一个子句中第三个参数是False（布尔值），因此函数f的第三个参数类型必须是Bool。同时第一个子句返回第一个参数x，所以f的类型可初步写为：

f :: t1 -> t2 -> Bool -> t1

其中t1是第一个参数的类型（也是返回值类型），t2是第二个参数的类型。

步骤2：分析第二个子句的类型约束 #

第二个子句的返回值是maybe 42 (g y) x，这个值的类型必须和第一个子句的返回类型t1一致。

先回忆maybe的标准类型：

maybe :: c -> (d -> c) -> Maybe d -> c

• 第一个实参42是Int类型，因此c = Int，意味着maybe的返回类型是Int，所以t1 = Int（函数f的返回类型固定为Int）。
• 第二个实参g y的类型必须是d -> c（即d -> Int）。
• 第三个实参x（第二个子句的第二个参数）的类型是Maybe d。

步骤3：结合g的类型推导 #

已知g :: a -> [a] -> b，调用g y时，y作为g的第一个参数，因此g y的类型是[a] -> b。

结合步骤2中g y :: d -> Int的结论，可得：

• [a] = d（参数类型匹配）
• b = Int（返回值类型匹配）

同时，第二个子句中y是f的第三个参数，类型必须是Bool（和第一个子句的第三个参数类型一致），因此y :: a → a = Bool。

代入后：

• d = [Bool]
• 第二个子句中第二个参数x的类型是Maybe d = Maybe [Bool]，即t2 = Maybe [Bool]。

最终类型 #

整合所有约束，f的最一般类型为：

f :: Int -> Maybe [Bool] -> Bool -> Int

内容的提问来源于stack exchange，提问作者Loosos