On Mon, Oct 20, 2014 at 11:57 AM, Dimitri DeFigueiredo < defigueiredo@ucdavis.edu> wrote:
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?
I assume you're trying this with ghci or compiling without optimizations. In these scenarios GHC isn't doing anything clever at all, so there will be two separate calls to minimum_bug in each recursion. Using a variable ensures that this value is explicitly shared between the guard and the result in the list. This section of Parallel and Concurrent Programming in Haskell helped me understand Haskell's non-strict evaluation model: http://chimera.labs.oreilly.com/books/1230000000929/ch02.html#sec_par-eval-w... 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.
Because displaying the value doesn't have any recursion to it, since it's `x` and not `minumum_bug x`. You can walk through the execution. -- Original call minimum_bug [1, 2] -- Expand the first matching pattern minimum_bug (1:[2]) | 1 > minimum_bug [2] -- minimum_bug [2] is forced due to the guard -- Evaluate minimum_bug [2] minimum_bug [2] -> 2 -- Step back to the guard we were trying to evaluate minimum_bug (1:[2]) | 1 > 2 1 > 2 -> False -- Guard fails, go to the otherwise case | otherwise = 1 -> 1 The `1` is already in normal form, so `putStrLn . show` doesn't have to do any extra reductions. If you walk through with `minimum_bug [2, 1]` you'll end up with `minimum_bug [1]` as the result, which is not in normal form and thus requires additional evaluation when `putStrLn . show` attempts to display it. If you use a larger list and walk through, you can see that the amount of redundant evaluation explodes when the list is in descending order. -bob