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