Daniel Fischer
Let us rewrite the definition a little (looking only at the case for nonempty lists):
Variant 1: myCycle xs = foldr leftAdd [] [1 .. ] where leftAdd _ acc = xs ++ acc
foldr leftAdd [] [1 .. ] ~> leftAdd 1 (foldr leftAdd [] [2 .. ]) ~> xs ++ (foldr leftAdd [] [2 .. ]) ~> xs ++ (leftAdd 2 (foldr leftAdd [] [3 .. ])) ~> xs ++ (xs ++ (foldr leftAdd [] [3 .. ])) ~> xs ++ (xs ++ (xs ++ (xs ++ ...)))
Variant 2: myCycle xs = foldr rightAdd [] [1 .. ] where rightAdd _ acc = acc ++ xs
foldr rightAdd [] [1 .. ] ~> rightAdd 1 (foldr rightAdd [] [2 .. ]) ~> (foldr rightAdd [] [2 .. ]) ++ xs ~> (rightAdd 2 (foldr rightAdd [] [3 .. ])) ++ xs ~> ((foldr rightAdd [] [3 .. ]) ++ xs) ++ xs ~> (((... ++ xs) ++ xs) ++ xs
Thanks for the explanation. After reading your post, I practiced writing a few foldr's out by hand. It really helped me to understand what foldr was doing. The part that initially confused me was the step in the third line:
foldr rightAdd [] [1 .. ] ~> rightAdd 1 (foldr rightAdd [] [2 .. ]) ~> (foldr rightAdd [] [2 .. ]) ++ xs
In case any other beginner reads this thread and is confused by that, here's what's going on. In RWH foldr is defined on p. 94 like this: foldr step zero (x:xs) = step x (foldr step zero xs) Daniel Fischer's example is calling foldr like this: foldr rightAdd [] [1 .. ] matching the foldr definition to that foldr function call: foldr step zero (x:xs) foldr rightAdd [] [1 .. ] you can see that step is the function rightAdd, zero's value is [], x = 1, and xs = [2..]. Therefore, from the definition of foldr: foldr rightAdd [] [1..] = rightAdd 1 (foldr rightAdd [] [2..]) The right hand side of that equation is a function call to rightAdd. It specifies two arguments: the first argument is 1, and the second argument is the expression in the parentheses. Now, look at the definition of rightAdd:
rightAdd _ acc = acc ++ xs
rightAdd is a function that ignores its first argument, then concatenates xs to the right side of its second argument. Applying that to this function call: rightAdd 1 (foldr rightAdd [] [2..]) rightAdd ignores the first argument, the 1, and concatenates xs to the right side of its second argument, which in this case is the expression in parentheses, so you get: (foldr rightAdd [] [2..]) ++ xs Therefore: rightAdd 1 (foldr rightAdd [] [2..]) = (foldr rightAdd [] [2..]) ++ xs Then it's just a matter of expanding the expression in the parentheses a few more times until you understand what the pattern is.
Let us rewrite it a little more. Obviously, it doesn't matter which list is passed into foldr leftAdd [] , as long as it's infinite. So instead of passing [1 .. ], let us pass a simpler infinite list, say ones = 1:ones (or ones = repeat 1). Then the evaluation becomes
foldr leftAdd [] ones ~> foldr leftAdd [] (1:ones) ~> leftAdd 1 (foldr leftAdd [] ones) ~> xs ++ (foldr leftAdd [] ones)
foldr rightAdd [] ones ~> foldr rightAdd [] (1:ones) ~> rightAdd 1 (foldr rightAdd [] ones) ~> (foldr rightAdd [] ones) ++ xs
So variant 1 amounts to myCycle xs = let ys = xs ++ ys in ys and variant 2 to myCycle2 xs = let ys = ys ++ xs in ys
Now it should be easy to see why the first works, but not the second.
No. I could tell from the example at the beginning of your post that there was an infinite expression on the front of the result list, but I can't see that in those equations. What am I failing to recognize there?
And from the rewriting, we can read off another representation of cycle a fold. We have, for all lists ks, ms: ks ++ ms = foldr (:) ms ks
So we can write variant 1 as the snappy
myCycle xs = let ys = foldr (:) ys xs in ys
I can't understand that one. I'll have to write it out: definition of foldr so I can refer to it: foldr step zero (x:xs) = step x (foldr step zero xs) 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] So substituting into the last line: = 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 ys is defined to be: foldr (:) ys [1, 2] Therefore, that process goes on and on ad infinitum. Pretty slick. 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]?