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
So variant 1 amounts to myCycle xs = let ys = xs ++ ys in ys
i.e. myCycle xs = ys where ys = xs ++ ys or myCycle xs = xs ++ myCycle xs - "right recursion" - good (kind of) even under strict semantics - will actually construct an infinite list in memory (although useless under strict, since it'll never stop).
and variant 2 to myCycle2 xs = let ys = ys ++ xs in ys
i.e. myCycle2 xs = ys where ys = ys ++ xs or myCycle2 xs = myCycle2 xs ++ xs - "left recursion" - does nothing under both strict and non-strict semantics - just goes into infinite loop trying to figure out what to do but never gets to do anything really.
We have, for all lists ks, ms: ks ++ ms = foldr (:) ms ks
which then by direct application yields -- myCycle xs = xs ++ myCycle xs myCycle xs = foldr (:) (myCycle xs) xs
So we can write variant 1 as the snappy
myCycle xs = let ys = foldr (:) ys xs in ys
which is then just rewritable as: myCycle xs = ys where ys = foldr (:) ys xs or (arriving at the same result) myCycle xs = foldr (:) (myCycle xs) xs I find that "where" rewrites are easier to comprehend for me, more often than not. :) Cheers,