[Haskell-beginners] learning lazy evaluation

[Dimitri DeFigueiredo]

I found an interesting situation while making recursive calls that I am 
trying to understand. I re-wrote the 'minimum' function from the prelude 
as such:

minimum_bug :: (Ord a) => [a] -> a
minimum_bug  [x] = x
minimum_bug  (x:xs) | x > minimum_bug xs = minimum_bug xs
                     | otherwise          = x

(I understand I should be using something like "minbug xs = foldr1 min 
xs" for this, but bare with me)

The interesting thing is that the function has exponential time 
behavior. In a way, that makes sense as I am making two recursive calls. 
But I was expecting GHC to be smart enough to transform it into 
something like:

minimum_bug' :: (Ord a) => [a] -> a
minimum_bug'  [x] = x
minimum_bug'  (x:xs) | x > y      = y
                      | otherwise  = x
                         where y = minimum_bug' xs

(This one always works as expected)

I understand that lazy evaluation implies memoization in some cases.
When does GHC only use memoization to avoid this kind of behavior?

Another interesting fact is that in my simple tests the exponential 
behavior does NOT occur when I pass the function a list in sorted order.

main = do putStrLn "started - in order list"
           putStrLn $ show $ minimum_bug [1..30000]  -- no problem
           putStrLn "started - out of order list"
           putStrLn $ show $ minimum_bug [27,26..1]  -- don't do this 
with large numbers!
           putStrLn "done!"

It's not clear to me how the sorted list is able to escape the 
exponential slow down.


Cheers,


Dimitri