Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

GHC splitAt performance

Tags:

haskell

ghc

splitAt is implemented in GHC in this way:

splitAt n xs  =  (take n xs, drop n xs)
  1. So does, splitAt do double the work or is there some behind the curtain optimization?
  2. Furthermore, take and drop generate a recursive process. Why is that. After all they are library functions and beauty is not as important. Why aren't they implemented to create an iterative process?
like image 261
SmokyGotSmoked Avatar asked Dec 06 '13 09:12

SmokyGotSmoked


2 Answers

The definition you are looking at is the Haskell Report Prelude definition.

Quoting from that page (emphasis mine)

In this chapter the entire Haskell Prelude is given. It constitutes a specification for the Prelude. Many of the definitions are written with clarity rather than efficiency in mind, and it is not required that the specification be implemented as shown here.

So in the GHC source, when you see

#ifdef USE_REPORT_PRELUDE
    // Haskell report prelude definition here (inefficient)
#else
    // Efficient definition here
#endif

you should read the #else branch if you want to see the definition that will normally be used - unless you specifically ask for the Haskell Report definitions.

like image 170
Chris Taylor Avatar answered Sep 28 '22 18:09

Chris Taylor


Regarding your second question, recursive process are usually what you want when you're dealing with lists, because they're a spine-lazy data structure. Consider the following the code:

head (take 100 [1 ..])

If we follow the code, we'll eventually arrive to the following expression: 1 : take (100 - 1) [2 ..]. Since we're only interested in the head of the list, the recursive call to take is never evaluated. However if take were to be implemented as an iterative process, it would need to iterate through all 100 elements, even if only the first element is needed.

like image 45
Pedro Rodrigues Avatar answered Sep 28 '22 19:09

Pedro Rodrigues