Re to `optimization for list'

[Serge D. Mechveliani]

Joshua Haberman <joshua at reverberate.org>  writes on  2 Aug 2009 

> Hello, I'm quite new to Haskell, but experienced in other languages (C,
> Python, Ruby, SQL, etc).  I am interested in Haskell because I've heard
> that the language is capable of lots of optimizations based on laziness,
> and I want to learn more about that.
>
> I dug in with Project Euler problem #1, and wrote:
> 
> main = 
>  print (show (sum [x | x <- [3..999], x `mod` 3 == 0 || x `mod` 5 == 0]))
>
> So far so good, but I want to have some way of observing what
> optimizations GHC has performed.  Most notably, in this example I want
> to know if the list was ever actually constructed in memory.  The "sum"
> function only needs the elements one at a time, in order, so if Haskell
> and GHC are everything I've heard about them, I would fully expect the
> list construction to be optimized out.  :)
> [..]

Your example is rather complex to start with, because `sum' has rather a 
complex definition in the Haskell library.
Consider first a more pure example:

  main = putStr (shows (or' ys) "\n")
         where
         n  = 10^8
         ys = replicate n False

         or' :: [Bool] -> Bool
         or' []      = False
         or' (x: xs) = x || (or' xs)

(the functions `||' (disjunction) and `replicate' are of the library).
Compile it with   ghc --make -O  (for any occasion),  
and then, it will be evident that it takes a constant in  n  space 
(and stack) when running  (run it like this:   `./T +RTS -M1m -RTS' ).

I think, this is  not due to optimization  but due to the very definition 
of evaluation in Haskell -- Head Normal Form. 
Compute this by hand:

  or' (replicate 9 False) =
  or' (False: (replicate 8 False)) =
  False || (or' (replicate 8 False)) =   
  or' (replicate 8 False) =               -- by definition of ||
  ...
  or' [] =
  False.

This is just the definition of evaluation in the Haskell language.
In this example, the list under  or'  never expands further than for 2 
members.

Consider a more complex example (and more close to your example):

  main = putStr (shows (sum2 ys) "\n")
                      -- sum'
         where
	 n  = 10^7
	 ys = [1 .. n]

	 sum2 :: [Int] -> Int
	 sum2 xs = sm xs 0   where  sm []      s = s
                                    sm (x: xs) s = sm xs (s+x)
	 sum' :: [Int] -> Int
	 sum' []      = 0
	 sum' (x: xs) = x + (sum' xs)

(the function [n .. m] is of the library).
Compile it with   ghc --make -O,  
and then, it will be evident that  sum2  takes a constant in  n  space 
(and stack) when running  (run it like this:   `./T +RTS -M1m -RTS' ).
Let us investigate this.
Furst, compute this by hand with treating (+) as not of the library:

  sm [1 .. 4] 0 = 
  sm (1:[2 .. 4]) 0 = 
  sm [2 .. 4] (1+0) = 
  sm (2: [3 .. 4]) (1+0) = 
  sm [3 .. 4] (2+(1+0)) = 
  ...

It must accumulate an intermediate stack of size  O(n).
Why ghc-6.10.4 computes it in a constant space (and stack) ?

The following is my guess. 
And let the Haskell experts correct me, please.

In the  Haskell-98 library  it is defined that (+) is  strict  on the 
type of  Int  (right?).
Therefore, the compiler optimizes (1+0) by replacing it immediately with
1. Taking in account that all other parts are computed lazily, the 
evaluation of the  compiled program  is like this:

  sm [1 .. 4] 0 = 
  sm (1:[2 .. 4]) 0 = 
  sm [2 .. 4] (1+0) = 
  sm [2 .. 4] 1 = 
  sm (2: [3 .. 4]) 1 = 
  sm [3 .. 4] (2+1) = 
  sm [3 .. 4] 3 = 
  ...
So, it is the result of combining of the evaluation definition with
a certain compiler's optimization related to the strictness info for  
Int.(+).
Right?

As to  sum',  it still takes O(n) space -- in  ghc-6.10.4. 
I think, this is because it is difficult for a compiler to guess how 
strictness of  Int.(+)  may correlate to the definition of  sum'. 
Probably, it needs some kind of inductive reasoning about sum' to 
optimize it (for example) into  sum2.
Right ?

Regards,

-----------------
Serge Mechveliani
mechvel at botik.ru