两个相似的函数如何在Haskell中具有不同的多态类型？

Question

我几乎是Haskell的新手,所以如果我缺少关键概念,请指出.

让我们说我们有这两个功能:

fact n
     | n == 0 = 1
     | n > 0  = n * (fact (n - 1))

多态类型fact是(Eq t, Num t) => t -> t因为n在if条件中使用而n必须是有效类型才能进行==检查.因此t必须是a,Number并且t可以是类约束中的任何类型Eq t

fib n
    | n == 1 = 1
    | n == 2 = 1
    | n > 2  = fib (n - 1) + fib (n - 2)

那为什么多态类型fib是(Eq a, Num a, Num t) => a -> t？

我不明白,请帮忙.

Answer 1

Haskell总是旨在推导出最通用的类型签名.

现在fact,我们知道输出的类型应该与输入的类型相同:

fact n | n == 0 = 1
       | n > 0  = n * (fact (n - 1))

这是由于最后一行.我们用n * (fact (n-1)).所以我们使用乘法(*) :: a -> a -> a.因此乘法采用相同类型的两个成员并返回该类型的成员.由于我们乘以n和n输入,因此输出与输入的类型相同.因为我们使用n == 0,(==) :: Eq a => a -> a -> Bool所以我们知道这意味着输入类型应该具有Eq a =>,此外0 :: Num a => a.所以结果类型是fact :: (Num a, Eq a) => a -> a.

现在fib,我们看到:

fib n | n == 1 = 1
      | n == 2 = 1
      | n > 2  = fib (n - 1) + fib (n - 2)

现在我们知道n了Eq a, Num a,因为我们使用了n == 1和,而且(==) :: Eq a => a -> a -> Bool和1 :: Num a => a.但输入n永远不会直接用于输出.确实,最后一行有fib (n-1) + fib (n-2),但在这里我们使用n-1和n-2作为新呼叫的输入.这意味着我们可以安全地假设输入类型和输出类型独立地起作用.输出类型仍然有一个类型约束:: Num t这是因为我们返回1前两种情况,并且1 :: Num t => t,我们还返回两个输出的添加:fib (n-1) + fib (n-2),所以再次(+) :: Num t => t -> t -> t.

Answer 2

不同之处在于fact,您直接在算术表达式中使用参数,该算术表达式构成最终结果:

fact n | ...  = n * ...

IOW,如果你写出扩展的算术表达式,n它会出现在:

fact 3  ?  n * (n-1) * (n-2) * 1

这修复了参数必须与结果具有相同类型的原因,因为

(*) :: Num n => n -> n -> n

不是这样的fib:这里的实际结果只是由文字和子结构组成.IOW,扩展的表达式看起来像

fib 3  ?  (1 + 1) + 1

不在n这里,所以在论证和结果之间不需要统一.

当然,在这两种情况下,您还习惯于n决定此算术表达式的外观,但为此您只使用了与文字相等的比较,其类型未与最终结果相关联.

请注意,您还可以提供fib类型保留签名:(Eq a, Num a, Num t) => a -> t严格来说比一般(Eq t, Num t) => t -> t.相反,您可以fact通过使用转换函数将其设置为不需要输入和输出的类型相同:

fact' :: (Eq a, Integral a, Num t) => a -> t
fact' = fromIntegral . fact

这虽然没有Integer多大意义,因为它几乎是唯一可以可靠使用的类型fact,但要实现上述版本,您需要从中开始Integer.因此,如果有的话,您应该执行以下操作:

fact'' :: (Eq t, Integral a, Num t) => a -> t
fact'' = fact . fromIntegral

这也可以用作Int -> Integer,这有点合理.

我建议只保留签名(Eq t, Num t) => t -> t,只在实际需要的地方添加转换操作.还是真的,什么我建议是不要使用fact在所有 -这是一个非常昂贵的功能,在实践中是很少真正有用的; 大多数天真地以阶乘结束的应用程序实际上只需要像二项式系数那样的东西,并且这些应用程序可以在没有因子的情况下更有效地实现.