Haskell函数类型推广

ff29svar  于 2022-11-30  发布在  其他
关注(0)|答案(2)|浏览(115)

我正在学习一门 haskell 课程,因为我是一个初学者。有一个任务,我不能解决,虽然我尝试了很多次。
任务是确定以下功能的最一般类型:

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

假设我们知道g :: a -> [a] -> b
有人能帮我吗?谢谢
我试图确定y :: Bool, g :: Bool -> [Bool] -> b(?),但我不确定“x”应该是什么,因为从第一行开始,我们可以说它可以是maybe 42 (g y) x,但表达式中还有一个“x”。
所以f的类型可能是f :: [Bool] -> [Bool] -> Bool -> [Bool]

icnyk63a

icnyk63a1#

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

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

我们看到第三个参数与False匹配,因此是Bool,因此是c ~ Bool。第一个子句也将第一个参数赋给x,并返回x,因此这意味着第一个参数的类型a和返回类型d是相同的,因此是a ~ d
我们知道maybe的类型为maybe :: f -> (e -> f) -> Maybe e -> f42是第一个参数,因此类型为f。整型字面值可以为任何Num类型,因此我们知道Num f。由于maybe 42 (g y) x的返回类型也是f,并且我们知道它也是a,因此我们知道f ~ amaybe 42 (g y) x中的第三个参数是x,这是f调用中的 * 第二个 * 参数(不要与第一个子句混淆),因此我们知道b ~ Maybe e
我们还可以看到一个调用g yg :: g -> [g] -> hg y的类型应该与maybe调用的第二个参数的类型相匹配,因此这意味着e ~ [g]a ~ hyg y调用中具有Bool类型,因此这意味着g ~ Bool,并且因此x1M35N1X函数具有类型x1M36N1X。
现在,我们已经收集了以下类型和等价物:

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确认了该类型。

wfveoks0

wfveoks02#

首先要认识到,对于任何方程,方程中定义的任何变量都只限于该方程。特别是,这意味着第一行中的x与第二行中的x没有任何关系。这是两个独立的变量,只是碰巧有相同的名称。
现在,你已经正确地确定了y :: Boolg :: 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] -> Intx :: Maybe [Bool](因为它被用作maybe的第三个参数)。
最后,从第二个等式中,我们可以看到函数的返回类型是maybe返回的值,也就是Int,因此,这也是第一个参数的类型,因为它在第一个等式中返回。
把所有这些放在一起:

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

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

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

相关问题