如果我像这样写一个递归因子:
fact 0 = 1
fact n = n * (fact (n-1))
ghci告诉我它有类型(Eq p, Num p) => p -> p.
我希望Haskell能够变得聪明,并使这个阶乘实现变得更快.所以,如果我写:fact (10 :: Int)所有这些都是用Ints 快速数学,如果我写fact (1000 :: Integer),所有或部分计算将是慢速数学与Integers.
ghci在这里很有帮助:
?: :t fact (2 :: Int)
fact (2 :: Int) :: Int
?: :t fact (2 :: Integer)
fact (2 :: Integer) :: Integer
我有两个问题:
Q1:跑步时会发生什么
?: fact (10 :: Int)
>3628800
?: fact (40 :: Int)
>-7060926325325235253252...
?: fact (66 :: Int)
>0
显然,Haskell无法为更大的参数计算正确的结果,因为它会溢出.所以我对结果并不感到惊讶fact 40,我得到了类似的结果fact 65.但是从fact 66函数开始总是返回0.为什么？
Q2:给定一个调用fact,所有对事实的递归调用都将使用相同的类型是正确的,即使在某些调用中Int可能已被替换为Integer(即整个计算速度比如果编译器能够在每次调用的基础上在Int和Integer之间的运行时决定.
Int是一个64位整数(至少在你的平台上),所以你看到的结果是模2 ^ 64(然后解释为有符号).fact 66是第一个恰好是倍数的因子2^64,因此fact 66 `mod` 2^64是0.因为每个阶乘都是先前阶乘的倍数,所有更大的阶乘也是倍数2^64.
给定事实调用,所有对事实的递归调用都将使用相同的类型是正确的
是的,类型*是Num a => a -> a -> a,这样的两个操作数*必须具有相同的类型,这也是它的结果的类型.因此,在n * fact (n-1),fact (n-1)必须具有相同的类型n(和n-1其也具有相同的类型n,因为-具有类型相同*).
我得到了类似的结果
fact 65.但是从fact 66函数开始总是返回0.怎么会？
好吧,如果fact对于给定的数字产生0,那么对于fact具有更大索引的每个其他数据,结果0也是如此,因为n * 0仍然如此0.类似的类型Int具有固定数量的比特(例如16比特Int16).如果我们将两个较大的数字相乘,产生一个超过16位的数字,则忽略较高的位.所以例如:
fact 7 | 5040 | 0001 0011 1011 0000
x 8 | x 8 | x 1000
------------------------------------------
40 320 | 40 320 | 1001 1101 1000 0000
------------------------------------------
-25 216 | -25 216 | 1001 1101 1000 0000
这里没有任何值被移出Int16,但由于签名解释,我们得到负值.稍后我们乘以9,然后得到:
fact 8 | -25 216 | 1111 1111 1111 1111 1001 1101 1000 0000
x 9 | x 9 | x 1001
---------------------------------------------------------------
40 320 | -226 944 | 1111 1111 1111 1100 1000 1001 1000 0000
---------------------------------------------------------------
-30 336 | -30 336 | 1000 1001 1000 0000
因此,CPU将在更大的寄存器(例如32位)中执行计算,并获取该结果的最低16位.由于每次乘以偶数,都会将值向左移动至少一个位置,因此设置位最终将从具有固定位数的整数表示中移出(尽管如果我们有更多位,则此过程将为当然需要更长时间).
对于具有n位的数,我们在小于2×n步中达到零(因为每次索引是偶数时,我们将它至少向右移位一个位置).
Q2:给定事实调用,所有对事实的递归调用都将使用相同的类型是正确的,即使在某些调用中Int可能已被替换为Integer也是如此
类型不是在运行时决定的(所以" 每次调用 "),而是在编译时.Haskell首先假设它的类型a -> b在哪里a并且b可以是任何类型来分析该函数.
接下来做一些分析:
fact 0 = 1
表示输入类型a和输出类型b必须是Num类型类.此外,我们执行隐式等式检查(好的Haskell将在(0 ==)幕后执行).所以现在我们知道类型是:
fact :: (Num a, Num b, Eq a) => a -> b
现在我们可以分析递归调用:
fact n = n * fact (n-1)
这相当于:
-- equivalent to
fact n = (*) n (fact (n-1))
哈斯克尔并没有认为这个递归fact调用有相同的类型.因此,递归调用具有类型(Num c, Num d, Eq c) => c -> d.
然而,我们可以分析功能(*) Num e => e -> e -> e.注意,在我们执行乘法时,在Haskell中,两个操作数和结果都具有相同的类型.由于第一个操作数是n,我们知道e ~ a和e ~ d(递归调用的结果类型)和e ~ b(我们的外部结果fact).所以我们知道e ~ a ~ b ~ d.这样就意味着a和b属于同一类型,因此fact具有类型:
fact :: (Num a, Eq a) => a -> a
因此我们知道,对于递归调用,c ~ d ~ a.因此递归调用也有类型fact :: (Num a, Eq a) => a -> a(递归函数调用).确实,这里递归调用使用相同的类型.