custom linked lists

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

instance Show a => Show (List a) where
    show Nil = ""
    show (Cons a Nil) = show a
    show (Cons a as) = show a ++ "," ++ show as

instance Functor List where
    fmap f Nil = Nil
    fmap f (Cons a as) = Cons (f a) (fmap f as)
    
instance Applicative List where
    (<*>) Nil _ = Nil
    (<*>) _ Nil = Nil
    (<*>) (Cons f fs) xs = fmap f xs `append` (<*>) fs xs
    pure x = Cons x Nil

instance Monad List where
    (>>=) Nil f = Nil
    (>>=) (Cons a as) f = f a `append` (>>=) as f
    return = pure

-- instance traversable
-- instance foldable

append :: List a -> List a -> List a
append Nil y = y
append x Nil = x
append (Cons x xs) y = Cons x $ append xs y

reverseL :: List a -> List a
reverseL Nil = Nil
reverseL (Cons a Nil) = Cons a Nil
reverseL (Cons a (Cons b bs)) = append (reverseL bs) (Cons b $ Cons a Nil)

-- push
-- pop
-- insertNth
-- init
-- last
-- head
-- tail
-- fromList
-- (!) , (!?)

showL :: Show a => List a -> String
showL l = "[" ++ show l ++ "]"

main = do
    putStrLn $ showL $ reverseL $ append (Cons 1 $ Cons 2 $ Cons 3 Nil) (Cons 4 $ Cons 5 Nil)
    putStrLn $ showL $ (+) <$> (Cons 1 $ Cons 2 Nil) <*> (Cons 3 $ Cons 4 Nil)
    putStrLn $ showL $ (Cons 3 $ Cons 4 Nil) >>= (\x -> Cons x $ Cons x Nil)
    putStrLn $ showL $ (Cons 3 $ Cons 4 Nil) >>= (\x -> pure $ x*2)