<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Oct 20, 2014 at 11:57 AM, Dimitri DeFigueiredo <span dir="ltr"><<a href="mailto:defigueiredo@ucdavis.edu" target="_blank">defigueiredo@ucdavis.edu</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">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:<br>
<br>
minimum_bug :: (Ord a) => [a] -> a<br>
minimum_bug [x] = x<br>
minimum_bug (x:xs) | x > minimum_bug xs = minimum_bug xs<br>
| otherwise = x<br>
<br>
(I understand I should be using something like "minbug xs = foldr1 min xs" for this, but bare with me)<br>
<br>
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:<br>
<br>
minimum_bug' :: (Ord a) => [a] -> a<br>
minimum_bug' [x] = x<br>
minimum_bug' (x:xs) | x > y = y<br>
| otherwise = x<br>
where y = minimum_bug' xs<br>
<br>
(This one always works as expected)<br>
<br>
I understand that lazy evaluation implies memoization in some cases.<br>
When does GHC only use memoization to avoid this kind of behavior?<br></blockquote><div><br></div><div>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.</div><div><br></div><div>This section of Parallel and Concurrent Programming in Haskell helped me understand Haskell's non-strict evaluation model: <a href="http://chimera.labs.oreilly.com/books/1230000000929/ch02.html#sec_par-eval-whnf">http://chimera.labs.oreilly.com/books/1230000000929/ch02.html#sec_par-eval-whnf</a></div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
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.<br>
<br>
main = do putStrLn "started - in order list"<br>
putStrLn $ show $ minimum_bug [1..30000] -- no problem<br>
putStrLn "started - out of order list"<br>
putStrLn $ show $ minimum_bug [27,26..1] -- don't do this with large numbers!<br>
putStrLn "done!"<br>
<br>
It's not clear to me how the sorted list is able to escape the exponential slow down.<br></blockquote><div><br></div><div>Because displaying the value doesn't have any recursion to it, since it's `x` and not `minumum_bug x`.</div><div><br></div><div>You can walk through the execution.</div><div><br></div><div>-- Original call</div><div>minimum_bug [1, 2]</div><div>-- Expand the first matching pattern</div><div>minimum_bug (1:[2]) | 1 > minimum_bug [2]</div><div>-- minimum_bug [2] is forced due to the guard</div><div>-- Evaluate minimum_bug [2]</div><div>minimum_bug [2]</div><div>-> 2</div><div>-- Step back to the guard we were trying to evaluate</div><div>minimum_bug (1:[2]) | 1 > 2</div><div>1 > 2</div><div>-> False</div><div>-- Guard fails, go to the otherwise case</div><div> | otherwise = 1</div><div>-> 1</div><div><br></div><div>The `1` is already in normal form, so `putStrLn . show` doesn't have to do any extra reductions.</div><div><br></div><div>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.</div><div><br></div><div>-bob</div><div><br></div><div><br></div></div></div></div>