prelude.tex

%\newpage

%\begin{center}
%	\vspace*{4cm}
%	\textbf{This page is intentionally left almost blank.}
%\end{center}

%\newpage

\begin{multicols}{2}\scriptsize 
	
	\textbf{\normalsize Appendix: Prelude}
	
	\begin{verbatim}
	class Eq a where
	  (==), (/=) :: a -> a -> Bool
	  x /= y = not (x == y)
	\end{verbatim}
	
	\begin{verbatim}
	class Eq a => Ord a where
	  (<), (<=), (>), (>=) :: a -> a -> Bool
	  min, max             :: a -> a -> Bool
	
	  min x y | x <= y    = x
	          | otherwise = y
	
	  max x y | x <= y    = y
	          | otherwise = x
	\end{verbatim}
	
	\begin{verbatim}
	class Enum a where
	  succ           :: a -> a 
	  pred           :: a -> a
	  toEnum         :: Int -> a
	  fromEnum       :: a -> Int 
	\end{verbatim}
	
	\begin{verbatim}
	class Bounded a where
	  minBound :: a 
	  maxBound :: a
	\end{verbatim}
	
	\begin{verbatim}
	class Num a where 
	  (+), (-), (*) :: a -> a -> a
	  negate        :: a -> a
	  abs           :: a -> a
	  signum        :: a -> a
	  fromInteger   :: Integer -> a
	\end{verbatim}
	
	\begin{verbatim}
	class Enum a => Integral a where 
	  quot      :: a -> a -> a
	  rem       :: a -> a -> a
	  div       :: a -> a -> a
	  mod       :: a -> a -> a
	  quotRem   :: a -> a -> (a, a)
	  divMod    :: a -> a -> (a, a)
	  toInteger :: a -> Integer
	\end{verbatim}
	
	\begin{verbatim}
	class Num a => Fractional a where
	  (/)          :: a -> a -> a
	  recip        :: a -> a
	  fromRational :: Rational -> a
	\end{verbatim}
	
	\begin{verbatim}
	data Int = ...
	  deriving ( Eq, Ord, Show, Read
	           , Num, Integral )
	\end{verbatim}
	
	\begin{verbatim}
	data Integer = ...
	  deriving ( Eq, Ord, Show, Read
	           , Num, Integral )
	\end{verbatim}
	
	\begin{verbatim}
	data Float = ...
	  deriving ( Eq, Ord, Show, Read
	           , Num, Fractional )
	\end{verbatim}
	
	\begin{verbatim}
	data Double = ...
	  deriving ( Eq, Ord, Show, Read
	           , Num, Fractional )
	\end{verbatim}
	
	\begin{verbatim}
	even :: Integral a => a -> Bool 
	even n = n `mod` 2 == 0
	\end{verbatim}
	
	\begin{verbatim}
	odd :: Integral a => a -> Bool 
	odd = not . even
	\end{verbatim}
	
	\begin{verbatim}
	class Show a where
	  show :: a -> String
	\end{verbatim}
	
	\begin{verbatim}
	class Read a where 
	  read :: String -> a
	\end{verbatim}
	
	\begin{verbatim}
	class Foldable t where
	  foldr   :: (a -> b -> b) -> b -> t a -> b
	  foldl   :: (b -> a -> b) -> b -> t a -> b
	  foldr1  :: (a -> a -> a) -> t a -> a
	  foldl1  :: (a -> a -> a) -> t a -> a
	  
	  null :: t a -> Bool 
	  null = foldr (\_ _ -> False) True
	  
	  length :: t a -> Int
	  length = foldr (\x r -> 1 + r) 0
	  
	  elem :: Eq a -> a -> t a -> Bool 
	  elem x = foldr (\y r -> x==y || r) False
	  
	  maximum :: Ord a => t a -> a 
	  maximum = foldl1 max
	  
	  minimum :: Ord a => t a -> a 
	  minimum = foldl1 min
	  
	  sum :: Num a => t a -> a 
	  sum = foldl (+) 0
	  
	  product :: Num a => t a -> a
	  product = foldl (*) 1
	\end{verbatim}
	
	\begin{verbatim}
	(.) :: (b -> c) -> (a -> b) -> a -> c
	(.) f g x = f (g x)
	\end{verbatim}
	
	\begin{verbatim}
	id :: a -> a
	id x = x
	\end{verbatim}
	
	\begin{verbatim}
	const :: a -> b -> a
	const x _ = x
	\end{verbatim}
	
	\begin{verbatim}
	($!) :: (a -> b) -> a -> b
	f $! x = ...
	\end{verbatim}
	
	\subsection*{Functors}
	
	\begin{verbatim}
	class Functor f where 
	  fmap :: (a -> b) -> f a -> f b
	\end{verbatim}
	\begin{displaymath}
	\begin{array}{lrcl}
	\textbf{Identity} & \mathit{fmap}~\mathit{id} & = &  \mathit{id} \\
	\textbf{Fusion} & \mathit{fmap}~(f \circ g) & = & \mathit{fmap}~f \circ \mathit{fmap}~g
	\end{array}
	\end{displaymath}
	
	\subsection*{Applicatives}
	
	\begin{verbatim}
	class Functor f => Applicative f where 
	  pure  :: a -> f a
	  (<*>) :: f (a -> b) -> f a -> f b
	\end{verbatim}
	\begin{displaymath}
	\begin{array}{lr}
	\textbf{Identity} & \mathit{pure}~\mathit{id} <\!\!*\!\!> v = v \\ 
	\textbf{Homomorphism} & \mathit{pure}~f <\!\!*\!\!> \mathit{pure}~x \\& = \mathit{pure}~(f~x) \\
	\textbf{Interchange} & u <\!\!*\!\!> \mathit{pure}~y \\
	& = \mathit{pure}~(\$~y) <\!\!*\!\!> u \\
	\textbf{Composition} & \mathit{pure}~(\circ) <\!\!*\!\!> u <\!\!*\!\!> v <\!\!*\!\!> w  \\
	& = u <\!\!*\!\!> (v <\!\!*\!\!> w)
	\end{array}
	\end{displaymath}
	
	\subsection*{Monads}
	
	\begin{verbatim}
	class Applicative m => Monad m where 
	  return :: a -> m a
	  return = pure
	
	  (>>=) :: m a -> (a -> m b) -> m b
	\end{verbatim}
	
	\begin{displaymath}
	\begin{array}{lrcl}
	\textbf{Left identity} & \mathit{return}~a \bind f & = & f~a \\
	\textbf{Right identity} & m \bind \mathit{return} & = & m \\
	\textbf{Associativity} & (m \bind f) \bind g & = & \\ \multicolumn{2}{r}{ m \bind (\textbackslash x \to f~x \bind g)}
	\end{array}
	\end{displaymath}
	
	\subsection*{Booleans}
	
	\begin{verbatim}
	data Bool = True | False
	  deriving ( Bounded, Enum, Eq, Ord
	           , Read, Show )
	\end{verbatim}
	
	\begin{verbatim}
	not :: Bool -> Bool
	not True  = False
	not False = True
	\end{verbatim}
	
	\begin{verbatim}
	(&&) :: Bool -> Bool -> Bool
	True && True = True 
	_    && _    = False
	\end{verbatim}
	
	\begin{verbatim}
	(||) :: Bool -> Bool -> Bool
	False || False = False 
	_     || _     = True
	\end{verbatim}
	
	\begin{verbatim}
	and :: Foldable t => t Bool -> Bool 
	and = foldr (&&) True
	\end{verbatim}
	
	\begin{verbatim}
	or :: Foldable t => t Bool -> Bool 
	or = foldr (||) False
	\end{verbatim}
	
	\begin{verbatim}
	all :: Foldable t => 
	       (a -> Bool) -> t a -> Bool
	all p = and . foldr (\x xs -> p x : xs) []
	\end{verbatim}
	
	\begin{verbatim}
	any :: Foldable t => 
	       (a -> Bool) -> t a -> Bool
	any p = or . foldr (\x xs -> p x : xs) []
	\end{verbatim}
	
	\begin{verbatim}
	otherwise :: Bool
	otherwise = True
	\end{verbatim}
	
	\subsection*{Characters} 
	
	\begin{verbatim}
	data Char = ...
	\end{verbatim}
	
	\begin{verbatim}
	type String = [Char]
	\end{verbatim}
	
	\begin{verbatim}
	isLower :: Char -> Bool 
	isLower c = c >= 'a' && c <= 'z'
	\end{verbatim}
	
	\begin{verbatim}
	isUpper :: Char -> Bool 
	isUpper c = c >= 'A' && c <= 'Z'
	\end{verbatim}
	
	\begin{verbatim}
	isAlpha :: Char -> Bool 
	isAlpha c = isLower c || isUpper c
	\end{verbatim}
	
	\begin{verbatim}
	isDigit :: Char -> Bool 
	isDigit c = c >= '0' && c <= '9'
	\end{verbatim}
	
	\begin{verbatim}
	isAlphaNum :: Char -> Bool 
	isAlphaNum c = isAlpha c || isDigit c
	\end{verbatim}
	
	\begin{verbatim}
	isSpace :: Char -> Bool 
	isSpace c = c `elem` " \t\n"
	\end{verbatim}
	
	\begin{verbatim}
	ord :: Char -> Int 
	ord c = ...
	\end{verbatim}
	
	\begin{verbatim}
	chr :: Int -> Char 
	chr n = ...
	\end{verbatim}
	
	\begin{verbatim}
	digitToInt :: Char -> Int 
	digitToInt c | isDigit c = ord c - ord '0'
	\end{verbatim}
	
	\begin{verbatim}
	intToDigit :: Int -> Char 
	intToDigit n 
	  | n >= 0 && n <= 9 = chr (ord '0' + n)
	\end{verbatim}
	
	\begin{verbatim}
	toLower :: Char -> Char 
	toLower c 
	  | isUpper c =
	      chr (ord c - ord 'A' + ord 'a')
	  | otherwise = c
	\end{verbatim}
	
	\begin{verbatim}
	toUpper :: Char -> Char 
	toUpper c 
	  | isLower c =
	      chr (ord c - ord 'a' + ord 'A')
	  | otherwise = c
	\end{verbatim}
	
	\subsection*{Lists}
	
	\begin{verbatim}
	data [a] = [] | (:) a [a]
	  deriving (Eq, Ord, Show, Read)
	\end{verbatim}
	
	\begin{verbatim}
	instance Functor [] where 
	  fmap = map
	\end{verbatim}
	
	\begin{verbatim}
	instance Applicative [] where
	  pure x = [x]
	  
	  fs <*> xs = [f x | f <- fs, x <- xs]
	\end{verbatim}
	
	\begin{verbatim}
	instance Monad [] where 
	  xs >>= f = [y | x <- xs, y <- f x]
	\end{verbatim}
	
	\begin{verbatim}
	instance Foldable [] where 
	  foldr _ v []     = v 
	  foldr f v (x:xs) = f x (foldr f v xs)
	  
	  foldr1 _ [x]    = x 
	  foldr1 f (x:xs) = f x (foldr1 f xs)
	  
	  foldl _ v []     = v 
	  foldl f v (x:xs) = foldl f (f v x) xs
	  
	  foldl1 f (x:xs) = foldl f x xs
	\end{verbatim}
	
	\begin{verbatim}
	head :: [a] -> a 
	head (x:xs) = x
	
	tail :: [a] -> [a]
	tail (x:xs) = xs
	\end{verbatim}
	
	\begin{verbatim}
	last :: [a] -> a
	last [x]    = x
	last (x:xs) = last xs
	\end{verbatim}
	
	\begin{verbatim}
	init :: [a] -> [a]
	init [_]    = []
	init (x:xs) = x : init xs
	\end{verbatim}
	
	\begin{verbatim}
	map :: (a -> b) -> [a] -> [b]
	map f []     = []
	map f (x:xs) = f x : map f xs
	\end{verbatim}
	
	\begin{verbatim}
	filter :: (a -> Bool) -> [a] -> [a]
	filter p [] = []
	filter p (x:xs)
	  | p x       = x : filter p xs
	  | otherwise = filter p xs
	\end{verbatim}
	
	\begin{verbatim}
	lookup :: Eq k => k -> [(k,v)] -> Maybe v
	lookup x [] = Nothing
	lookup x ((y,v):ys)
	  | x == y    = Just v
	  | otherwise = lookup x ys
	\end{verbatim}
	
	\begin{verbatim}
	(!!) :: [a] -> Int -> a
	(x:xs) !! 0 = x
	(x:xs) !! n = xs !! (n-1)
	\end{verbatim}
	
	\begin{verbatim}
	take :: Int -> [a] -> [a]
	take 0 _      = []
	take n []     = []
	take n (x:xs) = x : take (n-1) xs
	\end{verbatim}
	
	\begin{verbatim}
	drop :: Int -> [a] -> [a]
	drop 0 xs     = xs 
	drop n []     = []
	drop n (x:xs) = drop (n-1) xs
	\end{verbatim}
	
	\begin{verbatim}
	takeWhile :: (a -> Bool) -> [a] -> [a]
	takeWhile _ [] = []
	takeWhile p (x:xs) 
	  | p x       = x : takeWhile p xs
	  | otherwise = []
	\end{verbatim}
	
	\begin{verbatim}
	dropWhile :: (a -> Bool) -> [a] -> [a]
	dropWhile _ [] = []
	dropWhile p (x:xs) 
	  | p x       = dropWhile p xs
	  | otherwise = x : xs
	\end{verbatim}
	
	\begin{verbatim}
	splitAt :: Int -> [a] -> ([a], [a])
	splitAt n xs = (take n xs, drop n xs)
	\end{verbatim}
	
	\begin{verbatim}
	span :: (a -> Bool) -> [a] -> ([a], [a])
	span p xs = 
	  (takeWhile p xs, dropWhile p xs)
	\end{verbatim}
	
	\begin{verbatim}
	repeat :: a -> [a]
	repeat x = xs where xs = x : xs
	\end{verbatim}
	
	\begin{verbatim}
	replicate :: Int -> a -> [a]
	replicate n = take n . repeat
	\end{verbatim}
	
	\begin{verbatim}
	iterate :: (a -> a) -> a -> [a]
	iterate f x = x : iterate f (f x)
	\end{verbatim}
	
	\begin{verbatim}
	zip :: [a] -> [b] -> [(a,b)]
	zip []     _      = []
	zip _      []     = []
	zip (x:xs) (y:ys) = (x,y) : zip xs ys
	\end{verbatim}
	
	\begin{verbatim}
	(++) :: [a] -> [a] -> [a]
	[]     ++ ys = ys
	(x:xs) ++ ys = x : (xs ++ ys)
	\end{verbatim}
	
	\begin{verbatim}
	concat :: [[a]] -> [a]
	concat = foldr (++) []
	\end{verbatim}
	
	\begin{verbatim}
	reverse :: [a] -> [a]
	reverse = foldl (\xs x -> x : xs) []
	\end{verbatim}
	
	\begin{verbatim}
	subsequences :: [a] -> [[a]]
	subsequences []     = [[]]
	subsequences (x:xs) = ys ++ map (x:) ys
	  where ys = subsequences xs
	\end{verbatim}
	
	\begin{verbatim}
	nub :: Eq a => [a] -> [a]
	nub []     = []
	nub (x:xs) = x : nub (filter (/= x) xs)
	\end{verbatim}
	
	\begin{verbatim}
	delete :: Eq a => a -> [a] -> [a]
	delete _ []     = []
	delete x (y:ys) 
	  | x == y    = ys
	  | otherwise = y : delete x ys
	\end{verbatim}
	
	\subsection*{Maybe}
	
	\begin{verbatim}
	data Maybe a = Nothing | Just a
	  deriving (Eq, Ord, Read, Show)
	\end{verbatim}
	
	\begin{verbatim}
	instance Functor Maybe where
	  fmap f Nothing  = Nothing
	  fmap f (Just x) = Just (f x)
	\end{verbatim}
	
	\begin{verbatim}
	instance Applicative Maybe where
	  pure x = Just x
	  
	  Nothing  <*> _ = Nothing
	  (Just f) <*> y = fmap f y
	\end{verbatim}
	
	\begin{verbatim}
	instance Monad Maybe where
	  Nothing  >>= f = Nothing
	  (Just x) >>= f = f x
	\end{verbatim}
	
	\subsection*{Either}
	
	\begin{verbatim}
	data Either a b = Left a | Right b
	\end{verbatim}
	
	\subsection*{Tuples}
	
	All tuples are instances of \texttt{Eq}, \texttt{Ord}, \texttt{Show}, \texttt{Read}.
	
	\begin{verbatim}
	fst :: (a, b) -> a
	fst (x,y) = x
	\end{verbatim}
	
	\begin{verbatim}
	snd :: (a, b) -> b
	snd (x,y) = y
	\end{verbatim}
	
	\begin{verbatim}
	curry :: ((a, b) -> c) -> a -> b -> c 
	curry f x y = f (x, y)
	\end{verbatim}
	
	\begin{verbatim}
	uncurry :: (a -> b -> c) -> (a, b) -> c
	uncurry f (x,y) = f x y
	\end{verbatim}
	
	\subsection*{IO}
	
	\begin{verbatim}
	data IO a = ...
	
	instance Functor IO where ...
	instance Applicative IO where ...
	instance Monad IO where ...
	\end{verbatim}
	
	\begin{verbatim}
	getChar :: IO Char
	getChar = ...
	
	getLine :: IO String
	getLine = ...
	
	putChar :: Char -> IO ()
	putChar c = ...
	
	putStr :: String -> IO ()
	putStr []     = return ()
	putStr (x:xs) = putChar x >> putStr xs
	
	putStrLn :: String -> IO ()
	putStrLn xs = putStr xs >> putChar '\n'
	
	print :: Show a => a -> IO ()
	print = putStrLn . show
	\end{verbatim}
	
	\subsection*{Type-level programming}
	
	The kind of types is denoted as \texttt{*}. 
	
	\begin{verbatim}
	data Nat = Zero | Succ Nat
	\end{verbatim}
\end{multicols}