使函数的类型取决于输入

Question

所以我注意到在n = 20之后,LearnYouAHaskell(下面)中给出的阶乘函数因为Int类型的有限工作范围而缩小.

factorial :: Int -> Int
factorial 0 = 1
factorial n * factorial (n-1)

使用factorial :: Integer -> Integer修复问题很好,但它让人想起了这个问题.假设整数比Int稍微慢一点(我知道我在这里捏便士)我希望我的阶乘函数只在输入大于20时才使用Integer并保留Int->Int较小数字的类型.似乎应该有一个优雅的解决方案,使用if-then-else或警卫,但继续运行语法胡椒(错误消息)

Answer 1

您可以通过使用和类型并在需要时增长或Integer在某些情况下将演员延迟到最后来制作没有依赖类型的hackish解决方案.我不认为任何解决方案都会比使用更好Integer- 不要害怕Integer,gmp和mpir都相当不错.

铸造解决方案类似于:

selectiveFactorial :: Integer -> Integer
selectiveFactorial i
    | i < 20 = fromIntegral $ factorial (fromIntegral i :: Int)
    | otherwise = factorial i

factorial :: Integral a => a -> a
factorial 0 = 1
factorial n = n * factorial (n - 1)

Answer 2

正如Rein Henrichs所说,你可以用依赖类型的语言来做这些事情,而Haskell并没有(但是,相当).比如伊德里斯,它看起来就像是

factorial : (n : Int) -> if n <= 20 then Int else Integer
factorial n with (n <= 20)
  factorial n | True = thisfactorial n
  factorial n | False = thatfactorial n

但是你将如何使用这个结果呢？好吧,你需要进行比较才能找出所期望的类型,一旦说完所有,我就不知道你是怎么赢的.为了完整起见,使用网站看起来像这样:

use : Int -> Integer
use n with (factorial n)
  use n | fn with (n <= 20)
    use n | fn | False = fn
    use n | fn | True = cast fn

请注意,with条款的顺序很重要!该fn绑定都输入if n <= 20 then Int else Integer; 由于我不完全理解的原因,n <= 20测试必须在右边,以便模式匹配影响其类型.

Answer 3

它无法完成.但是你可以做些事情:

1. 使类型更通用:factorial :: Num a => a -> a; 这允许您的函数的用户决定他想要发生什么运行时惩罚以及允许的数字范围.

2. 使用类似的和类型data PossiblyBig = Small Int | Big Integer,然后有一个实现instance Num PossiblyBig,编码适合Intas的Small东西,以及不适合的东西Big; AFAIK Integer已经像这样工作(如果你想确切地知道,请查看GMP实现),所以这更像是一个典型的例子而不是关于在这种特殊情况下应该做什么的建议.