为什么在Haskell的Data.List中有两个'reverse'定义

Question

查看Data.List的来源显示reverse定义为

#ifdef USE_REPORT_PRELUDE
reverse                 =  foldl (flip (:)) []
#else
reverse l =  rev l []
  where
    rev []     a = a
    rev (x:xs) a = rev xs (x:a)
#endif

我想知道为什么提供第二个定义？它在某种意义上是否优越？

编辑:

正如下面的@nm评论,第二个版本"就像第一个版本的直接重写,foldl扩展并flip (:)内联到它." 实际上,Data.List本身定义foldl为

foldl        :: (b -> a -> b) -> b -> [a] -> b
foldl f z0 xs0 = lgo z0 xs0
             where
                lgo z []     =  z
                lgo z (x:xs) = lgo (f z x) xs

不可能知道Data.List的作者的动机(除非其中一个碰巧访问了这个页面),但作为一个初学者,如果我像第一个版本那样编写代码reverse并让编译器进行内联,那就没问题了.为了我？

Answer 1

我相信第一个版本,

reverse                 =  foldl (flip (:)) []

是Haskell报告中reverse定义的版本,第二个版本

reverse l =  rev l []
  where
    rev []     a = a
    rev (x:xs) a = rev xs (x:a)

是一个更有效的等效函数.你可以看到第二个版本使用了一个accum参数,所以整个事情都是一个尾调用,这在大多数Haskell实现上非常有效.

第二个版本是默认提供的版本,也许第一个版本是提供的,因此编译器编写者可以使用报告中更简洁的函数定义来测试程序执行的程度.

注意:似乎其他人得出了相同的结论,在一个帖子中haskell-cafe.

Answer 2

我们可以编译这两个版本的副本并查看 ghc 输出的内容。

module Rev where

myReverse1                 =  foldl (flip (:)) []
myReverse2 l =  rev l []
  where
    rev []     a = a
    rev (x:xs) a = rev xs (x:a)

构建以-ddump-simpl查看生成的核心，并-dsuppress-all消除一些不相关的噪音：

rwbarton@morphism:/tmp$ ghc -O -ddump-simpl -dsuppress-all -fforce-recomp Rev
[1 of 1] Compiling Rev              ( Rev.hs, Rev.o )

==================== Tidy Core ====================
Result size of Tidy Core = {terms: 40, types: 58, coercions: 0}

Rec {
myReverse3
myReverse3 =
  \ @ a_aNh z_aNB ds_aNC ->
    case ds_aNC of _ {
      [] -> z_aNB;
      : x_aNH xs_aNI -> myReverse3 (: x_aNH z_aNB) xs_aNI
    }
end Rec }

myReverse1
myReverse1 = \ @ a_aNh xs0_aNz -> myReverse3 ([]) xs0_aNz

Rec {
myReverse4
myReverse4 =
  \ @ a_aMV ds_dNu a1_auj ->
    case ds_dNu of _ {
      [] -> a1_auj;
      : x_auk xs_aul -> myReverse4 xs_aul (: x_auk a1_auj)
    }
end Rec }

myReverse2
myReverse2 = \ @ a_aMV l_auh -> myReverse4 l_auh ([])

myReverse3对 vs的检查myReverse4表明它们是相同的，只是它们以相反的顺序进行论证。事实上，您可以看到lgoinfoldl的参数与revin相反myReverse2。我很确定这不会导致明显的性能差异，如果有的话也是无意的。

所以，是的，通过优化，GHC 会将 的两个定义编译reverse为本质上相同的东西。我对内联定义存在原因的猜测是

• 大多数标准库的实现可以追溯到很久以前，并且曾经在 GHC、Hugs 和其他几个 Haskell 编译器之间共享。也许当时 GHC 或其他系统之一在优化方面不太擅长。

• 今天，在进行 GHC 开发时，拥有这些手动优化的版本仍然有点用处：在禁用优化的情况下构建编译器及其库是很常见的（因为它的速度明显更快），然后像这样的手动优化意味着生成的编译器，以及它生成的程序实际上更高效，我检查过，常见的“快速”BuildFlavour 仍然使用 构建库-O，所以这毕竟没有太多真相。