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

[7stud]

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?
Well, ys is equal to ys ++ [1, 2, 3].  So substituting
the value ys ++ [1, 2, 3] for ys in the right hand side
of the last line gives:

ys = (ys ++ [1, 2, 3]) ++ [1, 2, 3]
 
and then you need to substitute the value for ys
again on the right hand side, and so on ad infinitum.
That's bad because as in the earlier foldr example
ys is an infinite expression on the front of the list, and 
any operation on the list will cause haskell to try and evaluate 
that infinite expression.


> > myCycle2 [1, 2] =>
> > ys = foldr (:) ys [1, 2]
> > ---------------
> > Here's the left hand side of the foldr definition:
> > foldr step zero (x:xs)  =>match these parameters to the args in the call:
> > foldr   (:)    ys  [1, 2] =
> >
> > Now writing out what's on the right hand side of the equals sign in the
> > foldr definition using the args from the line above:
> > = (:) 1 (foldr (:) ys 2:[])
> > = 1:(foldr (:) ys 2:[])
> > Expand the term in the parentheses:
> > = 1:( (:) 2 (foldr (:) ys []) )
> > = 1:( 2:(foldr (:) ys []) )
> > = 1:2:(foldr (:) ys [])
> > = 1:2:(ys)
> > = 1:2:ys
> >
> > But ys is defined to be:
> >
> > foldr (:) ys [1, 2]
> 
> Actually, the implementation shouldn't need to go back to that definition at 
> this stage, it should now have reduced the thunk to
> ys = 1:2:ys
>

I figured haskell thunked the expression earlier than my last expansion: 

>= 1:2:(foldr (:) ys [1, 2])
>= 1:2:( (:) 1 (foldr (:) ys 2:[])
>= 1:2:(1:(foldr (:) ys 2:[])
>= 1:2:1:( (:) 2 (foldr (:) ys [])
>= 1:2:1:( 2:(foldr (:) ys [])
>= 1:2:1:2:(foldr (:) ys [])
>= 1:2:1:2:(ys)
>= 1:2:1:2:ys


but I wanted to keep expanding the expression to show that it was creating
an infinite cycle.

> , hopefully even by constructing a true cyclic list, making the ys on the 
> right hand side a pointer to the front of the list.
> >

Ok.

> > I guess haskell thunks the whole infinite expression, therefore
> > the let expression:
> >
> > let ys = ....
> > in ys
> >
> > doesn't cause an infinite loop in the ys = ... line, which means
> > the second line executes, which means ys is returned as the
> > result of the function call myCycle2 [1,2]?
> >
> >
> 
> Yes, it's thunked. It works because we can now determine the start of ys 
> without knowing anything about ys (provided that xs is nonempty). The result 
> of myCycle2 [1,2] is the thunk that says how to evaluate it. We give a name 
> to the result to be able to reference it in the calculation.
> 

Thanks again for the great explanations.