haskell - 给测量数据结构的函数赋予什么类型？整数，整数，积分？

Question

我有一个数据结构，例如表达式树或图形。我想添加一些“测量”功能，例如depth和 size .

如何最好地键入这些函数？

我认为以下三个变体的用处大致相同:

depth :: Expr -> Int

depth :: Expr -> Integer

depth :: Num a => Expr -> a

我有以下考虑:

我在看base和 fgl作为示例，他们一直使用 Int , 但是 Data.List还有genericLength等功能在返回类型中是多态的，我想也许添加这些 generic功能反射(reflect)了我可能应该尊重和加强的现代化趋势。

类似的想法在一些广泛使用的库中很明显，它们提供了具有相同功能的全面函数集，当用户可能需要返回类型的多个可能选择时(例如，xml-conduit 提供了同时接受惰性和ByteString 或 Text 的严格种类)。

Integer总体上比 Int 更好的类型有时我发现我需要将列表的长度转换为 Integer ，比如说因为在 Integer 中运行的算法需要考虑这个长度。

使函数返回 Integral意味着这些函数是多态的，并且可能会降低性能。我不太了解所有细节，但据我所知，可能会有一些运行时成本，而且多态的东西更难内存。

公认的最佳实践是什么？其中哪一部分是由于遗留和兼容性考虑？ (即如果 Data.List 是今天设计的，那么 length 之类的函数会有什么类型？)我错过了任何优点和缺点吗？

Answer 1

简短回答:作为一般规则，使用 Int ，如果您需要将其转换为其他内容，请使用 fromIntegral . (如果您发现自己经常进行转换，请定义 fi = fromIntegral 以节省输入或创建自己的包装器。)

主要考虑的是性能。您想编写算法，以便它在内部使用有效的整数类型。提供Int对于您正在执行的任何计算都足够大(标准保证有符号的 30 位整数，但即使在使用 GHC 的 32 位平台上，它也是有符号的 32 位整数)，您可以假设它将是高速的平台上的整数类型，特别是与 Integer 相比(它具有无法优化的装箱和 bignum 计算开销)。请注意，性能差异可能很大。使用 Int 的简单计数算法通常会快 5-10 倍与 Integer 相比s。

虽然你可以给你的函数一个不同的签名:

depth :: Expr -> Integer
depth :: (Num a) => Expr -> a

但实际上使用高效的 Int 在后台实现它键入并在最后进行转换，使转换隐式让我觉得这种做法很糟糕。特别是如果这是一个库函数，请明确 Int通过使其成为签名的一部分而在内部使用，这让我觉得更明智。

关于您列出的注意事项:

一、 generic* Data.List 中的函数不是现代的。特别是， genericLength可用 GHC 0.29 , 1996 年 7 月发布。在之前的某个时间点， length已根据 genericLength 定义，简单地说:

length :: [a] -> Int
length = genericLength

但在 GHC 0.29 中，这个定义被注释掉了 #ifdef USE_REPORT_PRELUDE ，以及 length 的几个手动优化变体是独立定义的。其他 generic*函数不在 0.29 中，但在 GHC 4.02 (1998) 中已经存在。

最重要的是，当 Prelude length 的版本从列表概括为 Foldable s，其中 是 一个相当近期的发展(从 GHC 7.10 开始？)，没有人愿意对 genericLength 做任何事情。 .我也不认为我曾在任何严肃的 Haskell 代码中“在野外”使用过这些函数。在大多数情况下，您可以将它们视为已弃用。

二、lazy/strict和 ByteString的使用/ Text库中的变体代表了一种不同的情况。特别是， conduit-xml用户通常会在惰性变体和严格变体之间以及 ByteString 之间做出决定。和 Text类型基于对正在处理的数据的考虑以及影响深远并遍及给定程序的整个类型系统的算法的构造。如果使用 conduit-xml的唯一方法|带着懒惰的 Text type 是将其逐个转换为严格 ByteString s，把它传给库，然后把它拉回来，转换回一个懒惰的 Text类型，没有人会接受这种复杂性。相比之下，单态 Int -基于 depth 的定义工作正常，因为您只需要 fromInteger . depth使其适应任何数字上下文。

第三，如上所述， Integer从在您不关心性能的情况下具有任意精度的角度来看，它只是一种“更好”的类型。对于像 depth 这样的事情和 count在任何实际环境中，性能可能比无限精度更重要。

第四，我不认为运行时成本或内存失败应该是在这里选择多态或非多态版本时认真考虑的因素。在大多数情况下，GHC 将在记忆化没有问题的情况下生成多态函数的专用版本。

在此基础上，我怀疑如果 Data.List是今天设计的，它仍然会使用 Int s。