Looking at the source of Data.List shows reverse
defined as
#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?
EDIT:
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
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?
I believe that the first version,
reverse = foldl (flip (:)) []
is the version of reverse
defined in the Haskell Report, and the second version
reverse l = rev l []
where
rev [] a = a
rev (x:xs) a = rev xs (x:a)
is an equivalent function which is more efficient. You can see that the second version uses an accumulation parameter so the whole thing is a tail call, which is very efficient on most Haskell implementations.
The second version is the one provided by default, perhaps the first one is provided so that the compiler writers can test how well programs perform with the more concise function definitions in the report.
Note: it appears others came to the same conclusion, in a post to haskell-cafe.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With