A right-fold is of the same structure as []

List.hs

{-# LANGUAGE RankNTypes #-}

import Data.Monoid

data List a = 
  List (forall b. (a -> b -> b) -> b -> b)

instance Eq a => Eq (List a) where
  x == y =
    iso ~> x == iso ~> y

instance Show a => Show (List a) where
  show =
    show . (~>) iso

instance Ord a => Ord (List a) where
  x `compare` y =
    (iso ~> x) `compare` (iso ~> y)

instance Monoid (List a) where
  mempty =
    nil
  List x `mappend` y =
    x cons y

instance Functor List where
  fmap f (List fldr) =
    fldr ((.:) . f) nil

instance Monad List where
  return =
    (.: nil)
  List fldr >>= f =
    fldr (mappend . f) nil

safeHead ::
  a
  -> List a
  -> a
safeHead d (List fldr) =
  fldr const d

cons ::
  a
  -> List a
  -> List a
cons h (List t) =
  List (\f -> f h . t f)

filta ::
  (a -> Bool)
  -> List a
  -> List a
filta p (List fldr) =
  fldr (\a -> if p a then (a.:) else id) nil

(.:) ::
  a
  -> List a
  -> List a
(.:) =
  cons

nil ::
  List a
nil =
  List (const id)

data Iso a b =
  Iso {
    (~>) ::
      a
      -> b    
  , (<~) ::
      b
      -> a
  }

iso ::
  Iso (List a) [a]
iso =
  Iso
    (\(List fldr) -> fldr (:) [])
    (foldr cons nil)