haskell - 为什么 Haskell 可以在这个函数中推导出 [] 类型

Question

rho x = map (((flip mod) x).(\a -> a^2-1)) (rho x)

此函数将生成一个无限列表。而我在GHCi中测试，函数类型是

*Main> :t rho
rho :: Integral b => b -> [b]

如果我这样定义一个函数

fun x = ((flip mod) x).(\a -> a^2-1)

类型是

*Main> :t fun
fun :: Integral c => c -> c -> c

我的问题是，Haskell 如何将函数类型推断为 b -> [b]？我们在这个函数中没有任何 [] 类型的数据。谢谢!

Answer 1

map 具有以下类型:

map :: (a -> b) -> [a] -> [b]

因此，我们可以推断出 map 的参数类型:

(((flip mod) x).(\a -> a^2-1)) :: (a -> b)
(rho x) :: [a]

但是map的结果也是rho x的结果，所以:

(rho x) :: [b]

这意味着 a 和 b 是相同的类型，所以:

rho :: ? -> [b]

如果我们检查映射函数，并释放 x，我们会发现类型:

\x -> ((flip mod) x).(\a -> a^2-1) :: Integral b => b -> (b -> b)

Integral b => b 给出了 x 的类型，而 (b -> b) 统一了类型函数组合，所以我们知道这个 b 和前面的是一样的。

rho :: Integral b => b -> [b]