Thank you Rahul. This is very helpful.
Rohan Sumant
On Wed, Apr 6, 2016 at 11:26 AM, Rahul Muttineni
Hi Rohan,
The definition of Prelude.head is
head :: [a] -> a head (x:_) = x head [] = undefined -- not exactly true but the details are irrelevant here
This is the same as
head :: [a] -> a head xs = case xs of (x : xs) -> x [] -> undefined
(Remeber that a list type can be thought of as data [a] = x : xs | [], hence (:) and [] are both data constructors.)
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.
(++) [] ys = ys (++) (x:xs) ys = x : xs ++ ys
This is the same as
(++) xs ys = case xs of [] -> ys x:xs -> x : (xs ++ ys)
Hence, evaluting ([1..] ++ [10]) will give 1 : ([2..] + [10]) which is in WHNF, hence head ([1..] ++ [10]) = 1.
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.
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.
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.
Hope that helps! Rahul Muttineni
_______________________________________________ Beginners mailing list Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners