-- 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)