时间戳

首页 > 解决方案 > 用newtype构造函数映射有什么作用

haskell - 用newtype构造函数映射有什么作用

问题描述

在思考类型fmap Sum的第 8 章中，我了解到

fastSum :: [Int] -> Int
fastSum = getSum . mconcat . fmap Sum

有O(n)运行时成本，而使用coerce反而避免了这种开销。

我知道newtypes 没有表示开销，但我不明白将 newtype 构造函数映射到列表的运行时效果是什么。我认为这只会产生编译时开销，而且应该只是O(1)，因为编译器只需要知道fmap SomeNewtypeCtr表达式的类型。

标签： haskellnewtype

解决方案

由于优化，很难理解 Haskell 在这种情况下究竟做了什么。Haskell 只规定结果是什么，而不是如何获得。

一些可能性：

  • fmap Sum执行列表扫描，并复制每个单元格和每个元素；
  • fmap Sum执行列表扫描，并复制每个单元格但不复制元素（新单元格指向旧元素）；
  • fmap Sum根本不扫描列表并自动优化为无操作。

我尝试了 godbolt.org来检查生成的核心和程序集。请注意，它仍然使用旧的 GHC 8.6.2。尽管如此，我还是打开了优化 ( -O2) 并编译了

foo :: [Int] -> [Sum Int]
foo = fmap Sum

并获得

foo = Example.foo1 `cast` (.....)
Example.foo1 = \ (v_a1iF :: [Int]) -> v_a1iF

因此foo成为恒等函数，适当强制，产生程序集

   movq %r14,%rbx
   andq $-8,%rbx
   jmp *(%rbx)

粗略地说，这应该相当于 GHC 运行时系统中的立即返回。

结论：Data.Coerce.coerce非常好，因为它确保了无操作，但即使是普通的 Haskell，在优化后也可以非常高效。

推荐阅读