为数据结构度量函数选类型：Int、Integer还是Integral？

这确实是Haskell里设计API时经常会纠结的问题，我结合社区的最佳实践和你的分析来拆解一下：

1. 优先选Int：大多数场景的默认选择 #

• 为什么base和fgl这类主流库都坚持用Int？首先是性能：Int是机器原生字长的整数，运算速度比多态函数或Integer快得多——尤其是像depth、size这类可能被频繁调用的度量函数（比如遍历整棵树/图时反复计算），性能差异会非常明显。
• 其次是API一致性：Haskell社区一直遵循“最小惊讶原则”，用户已经习惯了length :: [a] -> Int、Data.Map.size :: Map k v -> Int这类函数的返回类型，用Int能让你的API和现有生态对齐，减少用户的认知负担。
• 最后是内存效率：Int在内存里只占一个机器字，而Integer是任意精度的，会有额外的内存开销——对于绝大多数场景（比如普通树的深度、图的节点数），完全没必要用更重的Integer。

2. 什么时候考虑Integer？ #

• 当你明确知道度量值可能超出Int的范围时，比如处理极端庞大的树/图（深度或节点数达到百万级以上），或者后续的算法逻辑必须基于任意精度整数运算（就像你提到的场景）。
• 这里有个很实用的折中方案：可以同时提供两个版本的函数，比如depth :: Expr -> Int和depthInteger :: Expr -> Integer——就像xml-conduit同时支持懒/严格的ByteString或Text解析器一样，兼顾常用场景和特殊需求。

3. 关于多态返回类型（Num a => Expr -> a） #

• 你担心的性能损耗和记忆化问题是真实存在的：多态函数依赖约束字典的传递，运行时会有额外开销；而且记忆化（比如用MemoTrie实现缓存）对于多态函数会麻烦很多，因为要适配所有可能的Num实例，而单态函数的记忆化更直接高效。
• 什么时候适合用？如果你的库是通用工具类，且确实有用户需要将度量值转换成不同数值类型（比如转成Float做浮点运算），可以提供一个类似genericLength的genericDepth版本，但绝对不要把它作为唯一的API——因为90%以上的用户还是会用Int版本。
• 顺便说一句：genericLength的存在是补充而非替代，length依然是默认选择，就是因为它更快、更直观。

你问到如果现在重新设计Data.List，length会是什么类型？答案大概率还是Int——这不全是历史兼容的原因，更核心的是大多数场景下Int完全够用，而且性能和API一致性的优先级更高。genericLength是后来为了满足特殊需求添加的补充，而非推翻原有设计。

base库选择Int作为默认整数类型，早期确实有硬件适配和性能的历史考量，但到现在，这个选择依然符合现代Haskell“性能优先、API一致”的设计原则，所以它不是“历史包袱”，而是合理的设计决策。

优点补充 #

• 选Int的隐藏好处：错误反馈更早——如果度量值超出Int范围，开启编译选项后会直接触发溢出提示，帮你更早发现数据规模超出预期的问题；而Integer会默默处理大数值，可能掩盖潜在的性能或数据规模隐患。
• 提供多版本API：能同时满足不同用户的需求，普通用户用简单高效的Int版本，需要大数值的用户用Integer版本，高级用户用多态版本，这也是很多主流库的通用做法。

缺点补充 #

• 选Integer的额外问题：API不一致性——用户需要记住你的函数返回Integer，而其他相似函数（比如length）返回Int，增加了认知负担，还容易因为类型混用导致错误。
• 选多态类型的额外问题：类型推断复杂度——如果用户没有明确指定类型，GHC可能会推断出模糊的类型，需要手动加类型注解，降低了API的易用性。

总结一下最佳实践 #

1. 默认提供Int版本：覆盖绝大多数场景，保证性能和API一致性；
2. 按需提供Integer版本：针对明确需要大数值或Integer运算的场景；
3. 可选提供多态版本：作为补充，服务需要不同数值类型的高级用户，但不要作为默认。

内容的提问来源于stack exchange，提问作者Ignat Insarov