7stud
Daniel Fischer
writes: Am Donnerstag, 19. März 2009 20:32 schrieb 7stud:
Will Ness
writes: 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.
.............. I think you meant to say something like, "to see whether ws is an empty list and therefore foldr returns [1, 2, 3]:
foldr (:) [1,2,3] ws
foldr (:) [1,2,3] [] = [1,2,3]
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...
head (x:xs) = x ^^^^^^ the pattern head (foldr (:) [1,2,3] (foldr (:) [1,2,3] ws)) ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Although, I'm not seeing a pattern match here: the expression which is *trying*(?) to be matched against the pattern
I'll try again, please follow me here. We have these defintions: head (x:xs) = x foldr f z (a:as) = a `f` foldr f z as foldr f z [] = z First, the WRONG DEFINITION: zls = [1,2,3] ws = foldr (:) zls ws Why is it wrong? In Haskell, evaluation is pattern-matching. When the left hand side matches, right hand side IS the answer. That's one step, which gets repeated until we hit some primitive which stops this process. After loading these definitions, if we were to ask the top-level the value of (head ws), what would happen? The system tries to _reduce_ (head ws) ..... look! we have the definition { head (x:xs)=x } , it says to itself. OK, does its LHS (left hand side) match our expression? ----- head ws head (x:xs) ----- Now the system looks to see whether { ws ?= (x:xs) } can be matched. That means checking whether ws is a non-empty list. So the attempt to match 'ws' TRIGGERS the attempt to find out its value, to "reduce" its definition. Now, we have defined it as ws = foldr (:) zls ws Look! we have a definition for 'foldr' with LHS { foldr f z (a:as) }. Does it match our definition, the system asks itself? ----- foldr (:) zls ws foldr f z (a:as) ----- OK, f is (:), z is zls. No problem. WHAT ABOUT { ws ?= (a:as) } ? OOPS, we try to see what's ws's value in order to find out its value. INFINITE LOOP! Not because of any language feature, but because our definition defines itself immediately as itself. That's LEFT recursion. The good, RIGHT recursion, has some intervening case first, so that it'll make sense. Like, what is a natural number? "It's a number!" would be WRONG, LEFT RECURSIVE definition. But saying "It's either 1, or a successor of a natural number" is OK, because we have the terminal clause first ( which gives us an immediate answer, 1). So now, THE RIGHT DEFINITION: zls = [1,2,3] ws = foldr (:) ws zls Here, (head ws) _causes_ the system to check { ws ?= (x:xs) }, so again, its definition is looked into. It's defined in terms of foldr: foldr (:) ws zls -- our definition for 'w' foldr f z (a:as) -- LHS of 'foldr' definiton Do they match? Asks the system. OK, f is (:), z is ws. No problem, both are variables, so we don't need to look inside _their_ values just yet, nothing's forcing us to do that just yet. OK, so what's left is { zls ?= (a:as) }. Aha! No problem again, BECAUSE zls is KNOWN at this point already. So that's OK. Why the two definitions were different? ws = foldr (:) zls ws ws = foldr (:) ws zls Because, foldr is "forcing" in its last argument. Why? Because its definition is { foldr f z (a:as) = ... } so it TRIES TO MATCH ITS LAST ARGUMENT, i.e. it FORCES its value to be found. So we can't put our value that we're defining, into the forcing position of FOLDR call, because that would mean that our value is looked into in order to define its value, BEFORE it is defined. If it were looked into AFTER, there would be no problem. Cheers,