Haskell core list optimization

Question

Is any base list operation supported in Haskell (e.g. ghc) equivalent to their imperative counterparts?

For example, if I have a finite but calculated in the runtime list, is its length tied to this list, or should the calculation function (length xs) pass through the entire list recursively?

Is there any list of general Haskell optimizations (ghci or in general) created by the compiler?

Answer 1

Haskell performs very well on list optimization, but not the type you describe. Haskell does not have "special" list processing - they are similar to other regular Haskell types, albeit with some built-in syntactic sugar. This is nothing more special than

data List a = Nil | Cons a (List a) 

will be.

Haskell optimizes lists using what is called merge foldr / build, for example, optimizes map f (filter p list) so that it does not create an intermediate list for filter , but it does both the map and the filter in the same bypass. See here for more on what fuses are, or read here for more details on how this works.

In addition, more modern Haskell array libraries use a more aggressive type of merge, which can, for example, fuse sum (map f (enumFromN 0 n)) to a tail recursive iteration from 0 to n-1 , which is basically what you want to. Explore the package, this blog post for which thread you can make, and this document for details.

Answer 2

No, Haskell does not. If you calculate the following code:

 let x = [1..5] let y = [1..1000000] 

It takes longer to find the length of y than x , because y more values, and the compiler must count once to find the length of the list.