Haskell函数类型泛化

Question

我正在学习Haskell课程，因为我完全是初学者。有一个任务我虽然试了很多次也解决不了。

任务是确定下列函数的最一般类型:

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

假设我们知道g :: a -> [a] -> b

有人能帮我吗?谢谢你

我试着确定y :: Bool, g :: Bool -> [Bool] -> b(?)但是我不确定应该是什么。因为从第一行开始我们可以说它可以是maybe 42 (g y) x但还有一个&;x&;在表达式。

所以f的类型可能是f :: [Bool] -> [Bool] -> Bool -> [Bool]?

Answer 1

让我们从最泛型的类型开始:函数接受三个形参，因此返回一个项，因此我们首先假设f的类型为:

f :: a -> b -> c -> d

我们看到第三个参数与False匹配，所以是Bool，所以是c ~ Bool。第一个子句还将第一个参数赋值给x并返回x，因此这意味着第一个参数的类型a与返回类型d的类型相同，因此a ~ d.

我们知道maybe的类型是maybe :: f -> (e -> f) -> Maybe e -> f,42是第一个参数，所以类型是f。整数字面值可以是任何Num类型，因此我们知道Num f。由于maybe 42 (g y) x的返回类型也是f，我们知道这也是a，我们知道f ~ a，所以我们可以"专门化"。本例中maybe为maybe :: Num a => a -> (e -> a) -> Maybe e -> a。maybe 42 (g y) x中的第三个参数是x，这是f调用中的第二个参数(不要与第一个子句混淆)，因此我们知道b ~ Maybe e.

我们还看到g y与g :: g -> [g] -> h的调用。g y的类型应该与maybe调用的第二个参数的类型匹配，所以这意味着e ~ [g]和a ~ h。y在g y调用中具有类型Bool，因此这意味着g ~ Bool，因此g函数具有类型g :: Bool -> [Bool] -> a。

现在我们收集了以下类型和等价:

f :: a -> b -> c -> d
maybe :: f -> (e -> f) -> Maybe e -> f
g :: g -> [g] -> h
a ~ d
c ~ Bool
Num f
f ~ a
b ~ Maybe e
g ~ Bool
e ~ [g]
a ~ h
g ~ Bool

这意味着f的类型为:

f :: a -> b -> c -> d
-> f :: a -> b -> c -> a
-> f :: a -> b -> Bool -> a
-> f :: Num f => f -> b -> Bool -> f
-> f :: Num f => f -> Maybe e -> Bool -> f
-> f :: Num f => f -> Maybe [g] -> Bool -> f
-> f :: Num f => f -> Maybe [Bool] -> Bool -> f

因此最通用的类型是f :: Num f => f -> Maybe [Bool] -> Bool -> f，或者我们可以将参数重命名为f :: Num a => a -> Maybe [Bool] -> Bool -> a。

我们可以让ghci完成这项工作，例如:

ghci> import Data.Maybe
ghci> :{
ghci| g :: a -> [a] -> b
ghci| g = undefined
ghci| :}
ghci> :{
ghci| f x _ False = x
ghci| f _ x y     = maybe 42 (g y) x
ghci| :}
ghci> :t f
f :: Num p => p -> Maybe [Bool] -> Bool -> p

这意味着ghci确认了该类型。

Answer 2

首先要认识到的是，对于任何方程，在该方程中定义的任何变量，其作用域仅适用于该方程。特别是，这意味着第一行的x与第二行的x完全不相关。这是两个独立的变量，它们只是碰巧有相同的名称。

现在，您已经正确地确定了y :: Bool和g :: Bool -> [Bool] -> b对于一些未知的b。因此，g y :: [Bool] -> b

接下来要观察的是，由于maybe :: p -> (q -> p) -> Maybe q -> p，这意味着q ~ [Bool](来自g y的类型)和p ~ Int(来自字面量42)。因此，g :: Bool -> [Bool] -> Int和x :: Maybe [Bool](因为它被用作maybe的第三个参数)。

最后，从第二个等式中，我们可以看到函数的返回类型是maybe返回的值，即Int。因此，这也是第一个参数的类型，因为它是在第一个方程中返回的。

把所有这些放在一起:

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

最后一笔:我实际上撒了一点谎。文字42并不是真正的Int。这样的文字可以是具有Num类实例的任何类型。为了说明这一点，让我们用泛型类型替换签名中的Ints，并给该类型一个Num约束:

f :: Num a => a -> Maybe [Bool] -> Bool -> a