[Haskell-beginners] Re: folds again -- myCycle

[Will Ness]

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,