Haskell `List` standard instances implemented in terms of `foldr`

List.hs

data List a = Empty | Cons a (List a) deriving (Eq, Read, Ord, Show)

instance Foldable List where
  foldr _ acc Empty = acc
  foldr f acc (Cons x xs) = f x (foldr f acc xs)

instance Functor List where
  fmap f xs = foldr (\x acc -> Cons (f x) acc) Empty xs

instance Traversable List where
  traverse f xs = foldr (\x acc -> (fmap Cons $ f x) <*> acc) (pure Empty) xs

instance Monoid (List a) where
  mempty = Empty
  xs `mappend` ys = foldr Cons ys xs

instance Applicative List where
  pure x = Cons x Empty
  fs <*> xs = foldr (\f acc -> (fmap f xs) `mappend` acc) Empty fs

instance Monad List where
  xs >>= f = foldr (\x acc -> (f x) `mappend` acc) Empty xs

foldr is a catamorphism of List, which I'll explain in a blog post once I get around to learning what a "catamorphism" is.