Question about lazy evaluation
Hi, I am confused about this piece of explanation in Real World Haskell. -- file: ch08/append.hs (++) :: [a] -> [a] -> [a] (x:xs) ++ ys = x : (xs ++ ys) [] ++ ys = ys In a strict language, if we evaluate "foo" ++ "bar", the entire list is constructed, then returned. Non-strict evaluation defers much of the work until it is needed. If we demand an element of the expression "foo" ++ "bar", the first pattern of the function's definition matches, and we return the expression x : (xs ++ ys). Because the (:) constructor is non-strict, the evaluation of xs ++ ys can be deferred: we generate more elements of the result at whatever rate they are demanded. When we generate more of the result, we will no longer be using x, so the garbage collector can reclaim it. Since we generate elements of the result on demand, and do not hold onto parts that we are done with, the compiler can evaluate our code in constant space. When ('f' : "oo") ++ "bar" becomes 'f' : ("oo" ++ "bar") and then becomes 'f' : ('o' : ("o" ++ "bar")), we still need 'f', don't we? Best regards, Zhi-Qiang Lei zhiqiang.lei@gmail.com
Hi! Well, in your example you start with "foo" and "bar" and combine them to "foobar". The interesting part is that at the same rate you construct the result you're deconstructing the input. So: "foo" ++ "bar" -> "foo", "bar", "" (space for result) 'f' : ("oo" ++ "bar") -> "oo", "bar", "f" 'f' : ('o' : ("o" ++ "bar")) -> "o", "bar", "fo" ... As you can see the space requirements are constant. HTH, Thomas On 08.09.2011 07:56, Zhi-Qiang Lei wrote:
Hi,
I am confused about this piece of explanation in Real World Haskell.
-- file: ch08/append.hs (++) :: [a] -> [a] -> [a]
(x:xs) ++ ys = x : (xs ++ ys) [] ++ ys = ys In a strict language, if we evaluate "foo" ++ "bar", the entire list is constructed, then returned. Non-strict evaluation defers much of the work until it is needed.
If we demand an element of the expression "foo" ++ "bar", the first pattern of the function's definition matches, and we return the expression x : (xs ++ ys). Because the (:) constructor is non-strict, the evaluation of xs ++ ys can be deferred: we generate more elements of the result at whatever rate they are demanded. When we generate more of the result, we will no longer be using x, so the garbage collector can reclaim it. Since we generate elements of the result on demand, and do not hold onto parts that we are done with, the compiler can evaluate our code in constant space.
When ('f' : "oo") ++ "bar" becomes 'f' : ("oo" ++ "bar") and then becomes 'f' : ('o' : ("o" ++ "bar")), we still need 'f', don't we?
Best regards, Zhi-Qiang Lei zhiqiang.lei@gmail.com
_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners
On Thu, Sep 8, 2011 at 01:56, Zhi-Qiang Lei
When ('f' : "oo") ++ "bar" becomes 'f' : ("oo" ++ "bar") and then becomes 'f' : ('o' : ("o" ++ "bar")), we still need 'f', don't we?
Haskell lists are singly-linked lists, not arrays or double-linked lists or etc. Once we've evaluated past a given ":", there is no way to go back to what precedes it; it's no longer reachable (unless the caller, who has been passed the earlier part, is holding onto it) and the garbage collector will reclaim it. Put slightly differently: as you've phrased it, evaluation would expand each element but always start stepping into it from the very start. That's not what happens; as the evaluator steps through the list, it throws away its reference to the earlier part completely. So it never becomes 'f' : ('o' : ("o" ++ "bar"))) because when the evaluator is at the 'o' it has completely forgotten about the 'f'. It's got 'o' : ("o" ++ "bar") and any remaining reference (if there is one) to the 'f' is held by something else. -- brandon s allbery allbery.b@gmail.com wandering unix systems administrator (available) (412) 475-9364 vm/sms
participants (3)
-
Brandon Allbery -
Thomas -
Zhi-Qiang Lei