module Main where

newtype Fix f = Fix { unFix :: (f (Fix f)) }

data ListF a b = Nil | Cons a b deriving Functor
data WithSkip f a = Skip a | NoSkip (f a) deriving Functor

cata :: Functor f => (f a -> a) -> Fix f -> a
cata f = go where go = f . fmap go . unFix

ana :: Functor f => (a -> f a) -> a -> Fix f
ana f = go where go = Fix . fmap go . f

selectWhere_ :: (a -> Bool) -> ListF a b -> WithSkip (ListF a) b
selectWhere_ p Nil = NoSkip Nil
selectWhere_ p (Cons x xs)
  | p x = NoSkip (Cons x xs)
  | otherwise = Skip xs

selectWhereC :: (a -> Bool) -> Fix (ListF a) -> Fix (WithSkip (ListF a))
selectWhereC p = cata (Fix . selectWhere_ p)

selectWhereA :: (a -> Bool) -> Fix (ListF a) -> Fix (WithSkip (ListF a))
selectWhereA p = ana (selectWhere_ p . unFix)

countTo_ :: Int -> Int -> ListF Int Int
countTo_ n m
  | n == m = Nil
  | otherwise = Cons m (m+1)

countTo :: Int -> Fix (ListF Int)
countTo n = ana (countTo_ n) 0

sum'_ :: WithSkip (ListF Int) Int -> Int
sum'_ (Skip n) = n
sum'_ (NoSkip Nil) = 0
sum'_ (NoSkip (Cons n acc)) = n + acc

sum' :: Fix (WithSkip (ListF Int)) -> Int
sum' = cata sum'_

f1,f2,f3,f4 :: Int -> Int
f1 = sum' . selectWhereC even . countTo
f2 = sum' . selectWhereA even . countTo
f3 = cata (sum'_ . selectWhere_ even) . countTo
f4 n = sum' $ ana (selectWhere_ even . countTo_ n) 0

main = do
  print $ f1 42
  print $ f2 42
  print $ f3 42
  print $ f4 42
  print $ sum [x | x <- [0..41], even x]