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

[Daniel Fischer]

Am Donnerstag, 19. März 2009 20:32 schrieb 7stud:
> Will Ness <will_n48 <at> yahoo.com> 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?

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...

>  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 matched against the pattern