为什么在Haskell的Data.List中有两个"reverse"的定义 [英] Why two definitions of 'reverse' in Haskell's Data.List
问题描述
查看数据源.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
我想知道为什么提供第二个定义?从某种意义上说它优越吗?
I would like to know why the second definition is provided? Is it superior in some sense?
@ n.m.在下面的评论中，第二个版本像对第一个版本的简单重写，其中扩展了foldl并内嵌了flip (:)".实际上，Data.List本身将foldl定义为
As @n.m. comments below, the second version is "like a straightforward rewrite of the first version, with foldl expanded and flip (:) inlined into it." Indeed, Data.List itself defines foldl as
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的第一个版本的代码并离开就可以了编译器为我做内联吗?
It is impossible to know the motivation of the authors of Data.List (unless one of them happens to visit this page), but as a beginner is it OK if I write code like the first version of reverse and leave the compiler to do the inlining for me?
推荐答案
我们可以编译这两个版本的副本，并查看ghc的输出.
We can compile copies of these two versions and see what ghc outputs.
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进行构建以消除一些不相关的噪声:
Building with -ddump-simpl to see the generated core, and -dsuppress-all to eliminate some irrelevant noise:
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与myReverse4的检查表明它们是相同的，只是它们以相反的顺序接受其参数.实际上，您可以看到foldl中的lgo的自变量与myReverse2中的rev相反.我敢肯定，这样做不会导致明显的性能差异，如果不是故意的.
Examination of myReverse3 versus myReverse4 shows that they are the same, except that they take their arguments in the opposite order. Indeed, you can see that lgo in foldl has its arguments reversed from rev in myReverse2. I'm pretty sure there is no noticeable performance difference as a result of this, and if there is it's unintentional.
因此，是的，通过优化，GHC会将reverse的两个定义编译为本质上相同的东西.我对为什么存在内联定义的猜测是
So, yes, with optimizations GHC will compile the two definitions of reverse to essentially the same thing. My guesses for why the inlined definition exists are
-
大多数标准库的实现都可以追溯到很久以前，并且以前在GHC，Hugs和其他几个Haskell编译器之间共享.那时，GHC或其他系统之一可能在优化方面不太擅长.
The implementation of most of the standard library dates from a very long time ago and used to be shared between GHC, Hugs, and a couple of other Haskell compilers. Maybe GHC or one of the other systems was not so good at optimization back then.
在进行GHC开发时，拥有这些手动优化的版本今天仍然有点有用:在禁用优化的情况下编译编译器及其库是很平常的事(因为它的速度明显更快)，然后再进行手动优化，例如实际上，这意味着生成的编译器及其生成的程序效率更高，我检查了一下，常见的快速" BuildFlavour仍然使用-O来构建库，因此，毕竟这没有太多道理.
It's still slightly useful today to have these manually optimized versions, when doing GHC development: it's commonplace to build the compiler and its libraries with optimizations disabled (since it's significantly faster), and then manual optimizations like this one means the resulting compiler, and the programs it produces, are more efficient actually, I checked and the common "quick" BuildFlavour still builds the libraries with -O, so there is not much truth to this after all.
这篇关于为什么在Haskell的Data.List中有两个"reverse"的定义的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
