{-# 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)