[Haskell-beginners] Re: folds again -- myCycle
7stud
bbxx789_05ss at yahoo.com
Mon Mar 16 21:24:39 EDT 2009
Daniel Fischer <daniel.is.fischer <at> web.de> writes:
> 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]?
More information about the Beginners
mailing list