module List where

import Test.QuickCheck
import Test.QuickCheck.Checkers

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

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

instance Applicative List where
    pure f = Cons f Nil
    Nil <*> _ = Nil
    _ <*> Nil = Nil
    f <*> x = flatMap (\f' -> fmap f' x) f

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

fold :: (a -> b -> b) -> b -> List a -> b
fold _ b Nil = b
fold f b (Cons h t) = f h (fold f b t)

concat' :: List (List a) -> List a
concat' = fold append Nil

flatMap :: (a -> List b) -> List a -> List b
flatMap f as = concat' $ fmap f as

append' :: List a -> a -> List a
append' acc x = Cons x acc

fromList :: [a] -> List a
fromList xs = foldl (\l a -> Cons a l) Nil xs

instance Arbitrary a => Arbitrary (List a) where
    arbitrary = frequency [(1, pure Nil),
                           (5, Cons <$> arbitrary <*> arbitrary)]

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