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 必须是 Number 并且 t 可以是 class 约束内的任何类型 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

区别在于fact中，直接在构成最终结果的算术表达式中使用参数：

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

IOW，如果你写出展开的算术表达式，其中会出现n：

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

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

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

在 fib 中不是这样：这里的实际结果仅由文字和 sub-results 组成。 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 – 这是一个非常昂贵的函数，在实践中几乎没有真正用处；大多数天真地以阶乘结束的应用程序实际上只需要 binomial coefficients 之类的东西，并且可以在没有阶乘的情况下更有效地实现这些应用程序。

Answer 2

Haskell 始终旨在派生最泛型类型签名。

现在对于fact，我们知道输出的类型应该与输入的类型相同：

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

这是由于最后一行。我们使用 n * (fact (n-1))。所以我们使用乘法(*) :: a -> a -> a。因此，乘法需要两个相同类型的成员，并且 returns 是该类型的一个成员。由于我们乘以 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：这是因为前两种情况我们return 1，而1 :: Num t => t，我们也return 添加两个输出：fib (n-1) + fib (n-2)，所以又是(+) :: Num t => t -> t -> t.

Haskell 中两个相似的函数怎么会有不同的多态类型？

How can two similar functions have different polymorphic types in Haskell?

polymorphism

haskell

types

function

fibonacci