module RwhChap3
       where

import Data.List (sortBy,foldl')
import Test.QuickCheck
-- page 60

-- ex. 1
data List a = Cons a (List a)
            | Nil
              deriving (Show)

fromList Nil = []
fromList (Cons x xs) = x:fromList xs
-- fromList  (Cons 1 (Cons 2 (Cons 3 Nil)))

-- ex. 2
data TreeMaybe a = NodeMaybe a (Maybe (TreeMaybe a)) (Maybe (TreeMaybe a))
                   deriving (Show)


-- page 69-70

-- ex. 1 & 2
myLength :: [a] -> Int
myLength [] = 0
myLength (x:xs) = 1 + myLength xs
-- myLength [1,2,3] == length [1,2,3]

myLength2 :: [a] -> Int
myLength2 xs = foldl' (\ x y -> x+1) 0 xs

myLength3 :: [a] -> Int
myLength3 (x:xs) = (+) 1 $ myLength xs

-- ex. 3
myMean :: (Fractional b, Integral t) => [t] -> b
myMean [] = 0
myMean xs = fromIntegral(sum xs) / (fromIntegral $ length xs)

-- ex. 4
myPalindrome :: [a] -> [a]
myPalindrome [] = []
myPalindrome xs = xs ++ reverse xs
-- myPalindrom [1,2,3]

-- ex. 5
isPalindrome :: Eq a => [a] -> Bool
isPalindrome [] = False
isPalindrome (xs) | even (length xs) =
                      let nm = (length xs) `div` 2
                      in (take nm xs) == (reverse (drop nm xs))
isPalindrome xs = False

-- ex. 6
sortLists :: (Ord a) => [[a]] -> [[a]]
sortLists l = sortBy (\ p q -> (length p) `compare` (length q)) l

-- ex. 7 & 8
intersperse :: a -> [[a]] -> [a]
intersperse _ [] = []
intersperse s (x:xs) | null xs = x
                     | otherwise = x ++ [s] ++ (intersperse s xs)

-- ex. 9
data Tree a = Node a (Tree a) (Tree a)
            | Empty
              deriving (Show)

treeHeight :: Tree a -> Int
treeHeight Empty = 0
treeHeight (Node _ lt rt) = 1 + max (treeHeight lt) (treeHeight rt)

-- treeHeight Empty == 0
-- treeHeight (Node "x" Empty Empty) == 1
-- treeHeight (Node "x" Empty (Node "y" Empty Empty)) == 2