[Haskell-beginners] Re: folds again -- myCycle
Will Ness
will_n48 at yahoo.com
Tue Mar 24 16:21:33 EDT 2009
7stud <bbxx789_05ss <at> yahoo.com> writes:
>
> Daniel Fischer <daniel.is.fischer <at> web.de> writes:
> > Am Donnerstag, 19. März 2009 20:32 schrieb 7stud:
> > > Will Ness <will_n48 <at> yahoo.com> 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...
> >
> > > 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))
> > ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> > 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,
More information about the Beginners
mailing list