Am Samstag, 14. März 2009 08:57 schrieb 7stud:
I spent a long time working on a solution for an exercise in RWH: if you can, use foldr to mimic haskell's cycle function. At first, I wondered whether it was even possible. Then I worked on some ideas, and finally I came up with a solution. Surprisingly, my solution ended up being very simple:
myCycle [] = [] myCycle xs = helperFunc xs [1..] where helperFunc ys foldrXs = foldr accFunc [] foldrXs where accFunc _ acc = ys ++ acc
I tested it out, and it worked like a charm:
*Main> let x = myCycle [1, 2, 3] *Main> take 2 x [1,2] *Main> take 10 x [1,2,3,1,2,3,1,2,3,1] *Main> take 30 x [1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3]
After re-examining my solution, I decided that this line:
--where accFunc _ acc = ys ++ acc
read better like this:
--where accFunc _ acc = acc ++ ys
The altered function returns a list just fine. But when I use take on the list, I get a stack overflow. What is being thunked in both cases?
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 So in the first variant, where the cycled list is added to the front of the accumulator, the first elements of the list can be accessed before the accumulator is evaluated. In the second variant, the front of the result list is the accumulator, so it has to be evaluated before any part of the result can be accessed. Unfortunately, the front is an infinite nesting of concatenations, so its evaluation never finishes. The thing is that leftAdd is lazy in its second argument, while rightAdd is strict in it. If the accumulation function used in foldr is strict in its second argument, before any part of the result can be accessed, the whole list has to be traversed (which obviously will never finish for infinite lists). 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. And from the rewriting, we can read off another representation of cycle as 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
Thanks.
HTH, Daniel