<div dir="ltr">Thank you Rahul. This is very helpful.</div><div class="gmail_extra"><br clear="all"><div><div class="gmail_signature"><div dir="ltr"><div><br><br><br>Rohan Sumant<br>    </div></div></div></div>
<br><div class="gmail_quote">On Wed, Apr 6, 2016 at 11:26 AM, Rahul Muttineni <span dir="ltr"><<a href="mailto:rahulmutt@gmail.com" target="_blank">rahulmutt@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Hi Rohan,<div><br></div><div>The definition of Prelude.head is</div><div><br></div><div>head :: [a] -> a</div><div>head (x:_) = x</div><div>head [] = undefined -- not exactly true but the details are irrelevant here</div><div><br></div><div>This is the same as</div><div><br></div><div>head :: [a] -> a</div><div>head xs = case xs of</div><div>                   (x : xs) -> x</div><div>                   [] -> undefined</div><div><br></div><div>(Remeber that a list type can be thought of as data [a] = x : xs | [], hence (:) and [] are both data constructors.)</div><div><br></div><div>A case expression forces the evaluation of the scrutinee (xs in this case) and since xs = ([1..] ++ [10]), the expression is forced to evaluate to Weak Head Normal Form, which means it evaluates until it hits a data constructor or function. So this requires us to lookup the definition of (++) as well.</div><div><br></div><div><div>(++) []     ys = ys</div><div>(++) (x:xs) ys = x : xs ++ ys<br></div></div><div><br></div><div>This is the same as</div><div><br></div><div>(++) xs ys = case xs of</div><div>                  [] -> ys </div><div>                  x:xs -> x : (xs ++ ys)</div><div><br></div><div>Hence, evaluting ([1..] ++ [10]) will give 1 : ([2..] + [10]) which is in WHNF, hence head ([1..] ++ [10]) = 1.</div><div><br></div><div>So yes, you are correct, adding the (++) won't add the list until the evaluation "gets there", it will be stored as a thunk (suspended state). I suppose you can effectively consider that as "adding in constant time". But do note that it will consume quite a bit of memory over time to store the appends and the singleton lists.</div><div><br></div><div>Yes, list concatenation is O(n), but pushing to the end of the queue is not due to nature of laziness. This is precisely why it's hard to do running time analysis in the context of laziness. </div><div><br></div><div>But due note that in your particular example, appending to [1..] is futile since it's an infinite list, so that 10 will never actually get "seen" no matter how far you go in the list.</div><div><br></div><div>Hope that helps!</div><span class="HOEnZb"><font color="#888888"><div>Rahul Muttineni</div></font></span></div>
<br>_______________________________________________<br>
Beginners mailing list<br>
<a href="mailto:Beginners@haskell.org">Beginners@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners</a><br>
<br></blockquote></div><br></div>