If I for example apply map (just an example, could be filter or something else as well) on the same list 3 times, is Haskell going to pass through the list three times or only once? Example to run in ghci:

map ( 1) $ map (*2) $ map (^2) [1..100]

What I'm wondering is if the complexity is 3n where n is the size of the list as it would be in an imperative language, or if the laziness in Haskell optimizes it to 1n by only going through the list once, and doing the three operations on each element at the same time. So with 1 it would

1. raise it to 2
2. multiply it by 2
3. add 1

and then move on to the next element, instead of first going to through the whole list while raising every element to 2, then going through the list again and multiplying every element by and then go through the list a third time to increment every element by one.

So which is, it? Is Haskell going through the list 3 times or only once?

CodePudding user response：

You can do a simple check under ghci: set statistics mode on, and try running the expression both ways but with a significant size. Sum the list to force full evaluation.

Like this:

$ ghci
 GHCi, version 8.8.4: https://www.haskell.org/ghc/  :? for help
 λ> 
 λ> :set  s
 λ> 
 λ> n = 1000000
 (0.00 secs, 24,296 bytes)
 λ> 
 λ> sum ( map ( 1) $ map (*2) $ map (^2) [1..n] )
 666667666668000000
 (1.36 secs, 865,692,136 bytes)
 λ> 
 λ> sum ( map  (( 1) . (*2) . (^2))  [1..n] )
 666667666668000000
 (1.03 secs, 753,692,056 bytes)
 λ> 

So there is some performance gain in using the optimized expression, but it is much less than 3X.

Of course, for the sake of completeness you would have to check with GHC code compiled with -O2:

$ myHaskellExe  RTS -s -RTS
...