# [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
> >

We have these defintions:

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.

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?

-----
-----

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

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,

```