module HaskellFold where

mySumV1 [] = 0
mySumV1 (x:xt) = x + mySumV1 xt

myProductV1 [] = 1
myProductV1 (x:xt) = x * myProductV1 xt

myMap f [] = []
myMap f (x:xt) = f x : myMap f xt

myFoldr :: (a -> b -> b) -> b -> [a] -> b
myFoldr op z = g
  where
    g [] = z
    g (x:xt) = op x (g xt)

-- So here are mySumV1, myProductV1, myMap re-expressed as foldr's:
mySumFoldr xs = myFoldr (+) 0 xs
myProductFoldr xs = myFoldr (*) 1 xs
myMapFoldr f xs = myFoldr (\x r -> f x : r) [] xs


-- Sum a list, like the loop-and-accumulator you normally write:
mySumV2 xs = g 0 xs
  where
    -- If you want to use induction to prove g, use this specification:
    -- for all xs, for all a, g a xs = a + sum of xs
    g accum [] = accum
    g accum (x:xt) = g (accum + x) xt

-- Reverse a list, like the loop-and-accumulator you normally write:
myReverse xs = g [] xs
  where
    -- If you want to use induction, the specification is:
    -- for all xs, for all a, g a xs = (reversal of xs) ++ a
    g accum [] = accum
    g accum (x:xt) = g (x : accum) xt

myFoldl op a0 xs = g a0 xs
  where
    g accum [] = accum
    g accum (x:xt) = g (op accum x) xt

mySumFoldl xs = myFoldl (+) 0 xs

myReverseFoldl xs = myFoldl (flip (:)) [] xs


data MyList a = Nil | Cons a (MyList a) deriving (Eq, Show)

instance Foldable MyList where
    foldMap _ Nil = mempty
    foldMap f (Cons x xt) = f x <> foldMap f xt