<div dir="ltr">That is an interesting observation. Haskell is defined to have non-strict evaluation, which basically means the evaluation must happen from the outside in. It does not guarantee laziness, so even in interpreted settings it doesn't *have* to create a thunk. What you're seeing is simply an implementation detail of GHC that's consistent with the Haskell language but inconsistent with the expectation that it should be maximally lazy.</div><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Oct 20, 2014 at 2:18 PM, 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:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000">
Thanks Bob.<br>
<br>
The (lack of) exponential explosion makes sense now. And, yes, I was
using both ghci and ghc 7.6.3 without any flags.<br>
<br>
When memoization takes place is still a little murky to me, though.
<br>
Figure 2.2 in that chapter of Simon Marlow's book has the kind of
"aliasing" with the number '1' (two pointers pointing to the same
location) that I thought would also happen with 'minimum_bug xs' ,
but I guess 1::Int is a special case that is different from other
terms without optimization or the depiction is not accurate.<br>
<br>
I have a further question on that is troubling me. It seems that
constructors are treated differently from other expressions when it
comes to evaluation. The examples in the book show that:<br>
<br>
<pre>Prelude> let x = 1 + 2 :: Int
Prelude> :sprint x
x = _
</pre>
<br>
In other words, x is just an unevaluated thunk.<br>
But at the same time:<br>
<br>
<pre>Prelude> let x = 1 + 2 :: Int
Prelude> let z = (x,x)</pre>
<pre>Prelude> :sprint z
z = (_,_)</pre>
<br>
So, 'z' has been evaluated to WHNF.<br>
I was expecting to get:<br>
<br>
<pre>Prelude> :sprint z
z = _</pre>
<br>
Meaning, an unevaluated expression. Just like we did with 'x', but
it seems z has already been partially evaluated. Am I getting this
right? Are expressions with constructors evaluated differently? Why
is :sprint z different from 'z = _' in this case?<br>
<br>
<br>
Thanks again,<br>
<br>
<br>
Dimitri<div><div class="h5"><br>
<br>
<div>On 20/10/14 13:21, Bob Ippolito wrote:<br>
</div>
</div></div><blockquote type="cite"><div><div class="h5">
<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" target="_blank">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>
<br>
<fieldset></fieldset>
<br>
</div></div><span class=""><pre>_______________________________________________
Beginners mailing list
<a href="mailto:Beginners@haskell.org" target="_blank">Beginners@haskell.org</a>
<a href="http://www.haskell.org/mailman/listinfo/beginners" target="_blank">http://www.haskell.org/mailman/listinfo/beginners</a>
</pre>
</span></blockquote>
<br>
</div>
<br>_______________________________________________<br>
Beginners mailing list<br>
<a href="mailto:Beginners@haskell.org">Beginners@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/beginners" target="_blank">http://www.haskell.org/mailman/listinfo/beginners</a><br>
<br></blockquote></div><br></div>