Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why two definitions of 'reverse' in Haskell's Data.List

Tags:

haskell

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?

like image 204
Jyotirmoy Bhattacharya Avatar asked Jun 24 '14 15:06

Jyotirmoy Bhattacharya


1 Answers

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.

like image 138
Dietrich Epp Avatar answered Oct 07 '22 13:10

Dietrich Epp