listADT.hs

module ListADT where
import Data.List

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

-- instance (Show a) => Show (List a) where
--    show xs = "MyList[" ++ (intersperse ',' . map show) (toList xs) ++ "]"

instance Semigroup (List a) where
    a <> Nil = a
    Nil <> a = a
    (Cons x xs) <> b = Cons x (xs <> b)  

instance Monoid (List a) where
    mempty = Nil

instance Foldable List where

    foldr _ acc Nil = acc
    foldr f acc (Cons x xs) = x `f` foldr f acc xs

    foldMap f Nil = mempty
    foldMap f (Cons x xs) = f x <> foldMap f xs

instance (Eq a) => Eq (List a) where
    Nil == Nil = True
    Nil == _ = False
    _ == Nil = False
    (Cons x xs) == (Cons y ys) = x == y && xs == ys

fromList :: [a] -> List a
fromList = foldr Cons Nil

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

lengthList :: List a -> Integer
lengthList Nil = 0
lengthList (Cons x xs) = 1 + lengthList xs

avgList :: (Fractional a) => List a -> a
avgList Nil = 0 / 0
avgList xs = uncurry (/) . foldr (\z (x,y) -> (x+z,y+1)) (0,0)  $ xs



insertList :: (Ord a) => a -> List a -> List a
insertList a Nil = Cons a Nil
insertList a all@(Cons x xs) =
    if a > x then
        Cons x (insertList a xs)
    else
        Cons a all

insertListBy :: (a -> a -> Ordering) -> a -> List a -> List a
insertListBy _ a Nil = Cons a Nil
insertListBy cmp a all@(Cons x xs) =
    case cmp a x of
        GT -> Cons x (insertListBy cmp a xs)
        _  -> Cons a all 


sortList :: (Foldable t, Ord a) => t a -> List a
sortList = foldr insertList Nil

sortListBy f = foldr (insertListBy f) Nil

sortListOfLists :: (Foldable outer, Foldable inner) => outer (inner a) -> List (inner a) 
sortListOfLists = sortListBy (\x y -> compare (length x) (length y))

joinList :: a -> List (List a) -> List a
joinList _ Nil = Nil
joinList _ (Cons x Nil) = x
joinList sep (Cons x xs) = x <> Cons sep Nil <> joinList sep xs

data Tree a = Node a (Tree a) (Tree a)
            | Empty
              deriving (Show)

instance (Ord a) => Semigroup (Tree a) where
    a <> Empty = a
    Empty <> a = a
    left@(Node a b c) <> right@(Node d _ _) =
        if d > a then
            Node a b (c <> right)
        else
            Node a (b <> right) c

instance (Ord a) => Monoid (Tree a) where
    mempty = Empty

instance Foldable Tree where

    foldr _ acc Empty = acc
    foldr f acc (Node x xs xs') = x `f` foldr f (foldr f acc xs)  xs'

    foldMap f Empty = mempty
    foldMap f (Node x xs xs') = foldMap f xs <> f x <> foldMap f xs'


insertToTree v t = t <> Node v Empty Empty

treeFromFoldable :: (Foldable t, Ord a) => t a -> Tree a
treeFromFoldable = foldr insertToTree Empty

treeToList :: Tree a -> [a]
treeToList Empty = []
treeToList (Node a b c) = treeToList b ++ [a] ++ treeToList c


instance (Eq a) => Eq (Tree a) where
    t1 == t2 = treeToList t1 == treeToList t2