-- Let's figure out how lists work!

{- Lists are similarly said to be _polymorphic_, as the Maybe datatype was,
   because of this a right here
          |
          V    -}
data List a = Cons a (List a) | Nil deriving (Show, Eq)
{-             ^-- 1.  --^      ^- 2.
  1. Cons is a function that takes a value of type `a` and a value of type `List a` and returns a `List a`
  2. Is our identity or basis list: the empty list.

  Example:
  Cons 1 (Cons 2 Nil) is the same as [1,2] in normal haskell syntax
-}

-- Exercise 1.
-- Lists are functors so let's start by defining `fmap` as before
instance Functor List where
    fmap f Nil = Nil
    fmap f (Cons a b) = Cons (f a) (fmap f b)

-- Exercise 2.
-- Lists can be concatenated and added onto from the head
-- Fill in the definitions of these functions so that they work as described

-- Hint: prepend 1 Nil == ?
prepend :: a -> List a -> List a
prepend a (Cons b c) = Cons a (Cons b c)

-- Hint: concat (Cons 1 Nil) (Cons 2 Nil) == ?
concat :: List a -> List a -> List a
concat Nil a = a
concat (Cons a b) c = Cons a (concat b c)

main =  (print $ concat (Cons 1 (Cons 2 (Cons 3 Nil))) (Cons 4 (Cons 5 Nil))) >>
        (print $ prepend 3 (Cons 2 (Cons 1 (Cons 0 Nil))))