[Haskell-beginners] folds again -- myCycle

[Daniel Fischer]

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