List.hs

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

toList :: List a -> [a]
toList = foldr (\ x y -> x : y ) []

fromList :: [a] -> List a
fromList = foldr (\ x y -> Cons x y ) Nil

reverse' :: List a -> List a
reverse' = foldl (\ x y -> Cons y x) Nil

instance Monoid (List a) where
    mempty = Nil

    mappend xs ys = foldr (\ x acc -> Cons x acc) ys xs

instance Eq a => EqProp (List a) where
    (=-=) = eq

instance Functor List where
    fmap _ Nil         = Nil
    fmap f (Cons x xs) = Cons (f x) (fmap f xs)

instance Applicative List where
    pure x = Cons x Nil

    Nil       <*> _   = Nil
    _         <*> Nil = Nil
    Cons f fs <*> xs  = mappend (fmap f xs) (fs <*> xs)

instance Monad List where
    Nil       >>= _ = Nil
    Cons x xs >>= f = mappend (f x) (xs >>= f)

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

instance Traversable List where
    sequenceA = foldr (\ x acc -> Cons <$> x <*> acc) (pure Nil)