-- Code from Section 3.3 module Numbers where data Nat = Zero | Succ Nat toN :: Integer -> Nat toN = unfoldN (==0) pred fromN :: Nat -> Integer fromN = foldN 0 (+1) instance Show Nat where show = show . fromN foldN :: a -> (a->a) -> Nat -> a foldN z s Zero = z foldN z s (Succ n) = s (foldN z s n) -- part of the answer to Exercise 3.16, needed later on for hyloN' foldN' :: (Maybe a -> a) -> Nat -> a foldN' g = g . fmap (foldN' g) . predN iter :: Nat -> (a->a) -> (a->a) iter n f x = foldN x f n predN :: Nat -> Maybe Nat predN Zero = Nothing predN (Succ n) = Just n unfoldN' :: (a -> Maybe a) -> a -> Nat unfoldN' f x = case f x of Nothing -> Zero Just y -> Succ (unfoldN' f y) unfoldN :: (a -> Bool) -> (a -> a) -> a -> Nat unfoldN p f x = if p x then Zero else Succ (unfoldN p f (f x)) untilN :: (a -> Bool) -> (a -> a) -> a -> a untilN p f x = foldN x f (unfoldN p f x) hyloN' :: (Maybe a -> a) -> (a -> Maybe a) -> a -> a hyloN' f g = foldN' f . unfoldN' g untilN2 :: (a -> Bool) -> (a -> a) -> a -> a -> a untilN2 p f x y = foldN x f (unfoldN p f y)