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

[Will Ness]

7stud <bbxx789_05ss <at> yahoo.com> writes:

> 
> Daniel Fischer <daniel.is.fischer <at> web.de> writes:
> >
> >variant 2:
> >foldr rightAdd [] ones
> >   ~> foldr rightAdd [] (1:ones)
> >   ~> rightAdd 1 (foldr rightAdd [] ones)
> >   ~> (foldr rightAdd [] ones) ++ xs
> >
> >and variant 2 [amounts] to:
> >myCycle2 xs = let ys = ys ++ xs in ys
> >
> >Ah, well. I again underestimated how much experience one 
> >needs to see it immediately, sorry once more.
> 
> >The right hand side of myCycle2's definition (if we specialise
> >xs to, say, [1,2,3]) 
> 
> Ok, I see now. Using this definition:
> 
> >myCycle2 xs = let ys = ys ++ xs in ys
> 
> Then calling:
> 
> myCycle2 [1, 2, 3] 
> 
> You get:
> 
> let ys = ys ++ [1, 2, 3]
> 
> But what is the value of ys on the right hand side?
> ...
> and then you need to substitute the value for ys
> again on the right hand side, and so on ad infinitum.


Exactly! That's what's called LEFT recursion: the 'ys' in the re-write 
expression is ON THE LEFT SIDE of the expression, and so is immediately needed, 
before the lazyness of list-access has a chance to kick in. Note that the 
definition itself doesn't cause any infinite looping, only the actual list 
access will do that.

I would recommend first to think about Haskell code in terms of rewritable 
equivalence equations. Forget the supposed efficiency conserns, at first. Just 
think of definitions as of equations you can use to rewrite your expressions, 
in whichever order best suits you and assume the compiler will find the same 
way of simplifying your expression; and realize that simplification is 
triggered by _pattern_ _matching_ on _access_.

That is, until a value is needed at the top level, the definition is just a 
definition, dormant and ready to be used, nothing more - regardless whether 
it's implemented via thunks or not.

In our case, having 

head (x:xs) = x

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

let qs = foldr (:) qs [1,2,3]

head qs = head( foldr (:) qs [1,2,3] ) = head( 1:foldr (:) qs [2,3]) = 1

So remember just these two rules: 
1) the defintion is just a re-write equation, and 
2) a value is forced by being pattern matched 
- and you'll be fine.