{-# LANGUAGE GADTs #-}

data List a where
  Nil :: List a
  Cons :: a -> List a -> List a
  deriving Show

fromList :: [a] -> List a
fromList [] = Nil
fromList (x : xs) = Cons x $ fromList xs

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

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

instance Traversable List where
  sequenceA Nil = pure Nil
  sequenceA (Cons x xs) = (Cons <$> x) <*> sequenceA xs