{-# LANGUAGE GADTs #-} data Tree a where Empty :: Tree a Branch :: a -> Tree a -> Tree a -> Tree a -- treeSize :: forall a. Tree a -> Integer treeSize :: Tree a -> Integer treeSize Empty = (0 :: Integer) treeSize (Branch a l r) = 1 + treeSize l + treeSize r -- forall is like an extra argument -- caller gets to pick the type -- This promises to return any type of the *caller's* choosing! -- Can't be done. foo :: Integer -> a foo n = error (show n) f :: a -> a -> a -- f x y = x && y -- f xs ys = xs ++ ys f x y = x g :: a -> a -> a g x y = y -- q :: a -> a -- q x = -- if a==Int then x+1 else a -- Not allowed in Haskell! -- Polymorphic functions must work -- *uniformly* for any choice of type -- Can't make choices based on type -- at run time -- "Parametricity" -- "Parametric polymorphism" -- a -> a f1 :: a -> a f1 x = x -- "id" -- a -> b -- forall a. forall b. a -> b -- Impossible! -- a -> b -> a f2 :: a -> b -> a f2 x y = x -- "const" -- [a] -> [a] f3 :: [a] -> [a] f3 = reverse f3b :: [a] -> [a] f3b [] = [] f3b (x:xs) = xs f3c :: [a] -> [a] f3c _ = [] -- (b -> c) -> (a -> b) -> a -> c f4 :: (b -> c) -> (a -> b) -> a -> c f4 g h a = g (h a) -- (.) myMap :: (a -> b) -> [a] -> [b] myMap f [] = [] myMap f (x:xs) = f x : myMap f xs -- Folds -- foldr (&) z (a:b:c:[]) = a & (b & (c & z)) -- FOLDS REPLACE CONSTRUCTORS myFoldr :: (a -> b -> b) -> b -> [a] -> b myFoldr (&) z [] = z myFoldr (&) z (x:xs) = x & myFoldr (&) z xs data WeirdTree a where WEmpty :: WeirdTree a WBranch :: a -> Char -> WeirdTree a -> WeirdTree a -> WeirdTree a Stalk :: a -> WeirdTree a -> WeirdTree a -- Let's write a map for WeirdTree. treeMap :: (a -> b) -> WeirdTree a -> WeirdTree b treeMap f WEmpty = WEmpty treeMap f (WBranch a c l r) = WBranch (f a) c (treeMap f l) (treeMap f r) treeMap f (Stalk a t) = Stalk (f a) (treeMap f t) -- FOLDS REPLACE CONSTRUCTORS -- Let's write a fold for WeirdTree. treeFold :: (a -> Char -> b -> b -> b) -> b -> (a -> b -> b) -> WeirdTree a -> b treeFold f z g WEmpty = z treeFold f z g (WBranch a c l r) = f a c (treeFold f z g l) (treeFold f z g r) treeFold f z g (Stalk a t) = g a (treeFold f z g t)