Am Donnerstag, 19. März 2009 20:32 schrieb 7stud:
Will Ness
writes: In our case, having The access in (head ys) gets traslated in
head ys = head (ys ++ [1,2,3]) = head ((ys ++ [1,2,3]) ++ [1,2,3])
but for the other defintion
let zs = [1, 2, 3] ++ zs
it's
head zs = head([1, 2, 3] ++ zs) = head( (1:[2,3]) ++ zs) = head( 1:([2,3]++zs) ) = 1
according to the defintion of (++),
(x:xs)++ys = x:(xs++ys)
Were we to use the foldr definition, it'll get rewritten just the same, using the foldr definition (as long as it's not the left-recursive defintion):
foldr f z (a:as) = a `f` foldr f z as
let ws = foldr (:) [1,2,3] ws
head ws = head (foldr (:) [1,2,3] ws) = head (foldr (:) [1,2,3] (foldr (:) [1,2,3] ws))
because 'ws' is getting matched against (a:as) pattern in foldr definition, so is immediately needed, causing INFINITE looping. BUT
I'm confused by your statement that ws is getting matched against the (a:as) pattern in the foldr definition, and therefore it is immediately
evaluated. I didn't think the let expression:
let ws = foldr (:) [1,2,3] ws
would cause infinite looping.
Note this is again the left recursive bad definition. As long as we don't want to know anything about ws, the definition ws = foldr (:) [1,2,3] ws sleeps peacefully.
Wouldn't it be the head pattern that is being matched, and therefore head
triggers the evaluation?
Although, I'm not seeing a pattern match here:
head (x:xs) = x ^^^^^^ the pattern head (foldr (:) [1,2,3] (foldr (:) [1,2,3] ws)) ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
If we need to know about the structure of ws, for example if we query head ws the evaluation of ws is triggered. In the case of head, we want to know if ws matches the pattern (_:_), in which case head returns the head of ws, or not, in which case head throws an exception. So the implementation tries to match ws with the pattern (_:_). To see if it matches, it must evaluate ws, first replacing ws by the right hand side of its definition, foldr (:) [1,2,3] ws. Doesn't yet say if ws matches (_:_), so the foldr must be evaluated. foldr (:) [1,2,3] [] ~> [1,2,3] foldr (:) [1,2,3] (y:ys) = y:foldr (:) [1,2,3] ys To know which equation to use, the implementation tries to match ws with []. Unfortunately, there is no information about the structure of ws available yet. So ws is replaced by the right hand side of its definition to find out whether it matches [], leading to head (foldr (:) [1,2,3] (foldr (:) [1,2,3] ws)). Dang, to see whether the inner foldr returns an empty list or not, we need to know whether ws is empty or not, so we must replace ws in the inner foldr with the right hand side of its definition... the expression which is matched against the pattern