Haskell中div函数的计算成本是多少？

嘿，这个问题问到点子上了！我来给你拆解一下Haskell里div函数的计算成本，以及它对你的izq函数的影响~

首先得明确：Haskell的div成本取决于你用的整数类型（是固定大小的Int还是任意精度的Integer），还有你用的编译器（大部分人用的是GHC，我就以它为例啦）：

• 对于Int类型：这是对应机器硬件的固定长度整数，GHC会直接调用CPU的硬件除法指令。这种情况下，div的计算成本是常数时间O(1)——不管你的n是多大（只要在Int的范围内），执行除法的时间基本是固定的，不会随数字大小变化。
• 对于Integer类型：这是支持任意大小的大整数，它的除法实现是软件层面的算法。这种情况下，div的成本大概是O(k²)，其中k是数字的二进制位数（简单说就是数字越大，位数越多，除法运算的步骤就越多，耗时越长）。

再回到你的izq函数，先把代码贴出来方便看：

izq n   | even (n - 1)  = ((n - 1) `div` 2)
        | otherwise     = (((n - 1) `div` 2) + 1)

其实悄悄说一句，这个逻辑可以简化成izq n = (n + 1) div 2，不过这不影响成本分析~

针对你的函数的成本：

• 如果n是Int类型：判断even (n-1)是常数时间，加上后面的div和加法也都是O(1)，所以整个izq函数的计算成本就是O(1)。
• 如果n是Integer类型：div的成本占主导，所以整个izq的成本就是O(k²)，和n的位数正相关。

最后提一句：Haskell是惰性求值的，如果这个函数的结果没有被实际用到，可能不会触发计算；但一旦需要实际计算结果，就会遵循上面的成本模型哦。

备注：内容来源于stack exchange，提问作者Casta