
\section{Let's Implement λ-Calculus}
\subsection{}

\frame{\frametitle{\color{white} dummy}
  \begin{itemize}
    \item {\color{lightgray} What can Haskell do?}
    \item {\color{lightgray} What is λ-Calculus?}
    \item {\color{lightgray} Why Implement λ-Calculus?}
    \item {Let's Implement λ-Calculus}
    \item {\color{lightgray} Questions?}
    \item {\color{lightgray} References}
  \end{itemize}
}

\frame{\frametitle{First Expression and evaluate (\jref{https://github.com/godfat/sandbox/blob/master/haskell/fpug/01/00.lhs
}{source})}
\footnotesize
\usebeamerfont*{font DejaVu Sans Mono}
module Main where \\
\color{white}. \\
data Expression = Literal Integer \\
 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ | Plus Expression Expression \\
{\color{white}.} \\
evaluate :: Expression -> Integer \\
evaluate (Literal i) \ \ \ \ \ \ \ = i \\
evaluate (Plus expr0 expr1) = \\
 \ \ evaluate expr0 + evaluate expr1 \\
{\color{white}.} \\
test0 = evaluate (Literal 1) \\
test1 = evaluate (Plus (Literal 1) (Literal 2)) \\
test2 = evaluate (Plus (Plus (Literal 1) \\
 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (Literal 2)) \\
 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (Literal 3))
}

\frame{\frametitle{First Expression and evaluate (\jref{https://github.com/godfat/sandbox/blob/master/haskell/fpug/01/00.lhs
}{source})}
\footnotesize
\usebeamerfont*{font DejaVu Sans Mono}
module Main where \\
{\color{white}.} \\
data Expression = Literal Integer \\
 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ | Plus Expression Expression \\
\color{white}. \\
evaluate :: Expression -> Integer \\
evaluate (Literal i) \ \ \ \ \ \ \ = i \\
evaluate (Plus expr0 expr1) = \\
 \ \ evaluate expr0 + evaluate expr1 \\
{\color{white}.} \\
test0 = evaluate (Literal 1) \\
test1 = evaluate (Plus (Literal 1) (Literal 2)) \\
test2 = evaluate (Plus (Plus (Literal 1) \\
 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (Literal 2)) \\
 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (Literal 3))
}

\frame{\frametitle{First Expression and evaluate (\jref{https://github.com/godfat/sandbox/blob/master/haskell/fpug/01/00.lhs
}{source})}
\footnotesize
\usebeamerfont*{font DejaVu Sans Mono}
module Main where \\
{\color{white}.} \\
data Expression = Literal Integer \\
 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ | Plus Expression Expression \\
{\color{white}.} \\
evaluate :: Expression -> Integer \\
evaluate (Literal i) \ \ \ \ \ \ \ = i \\
evaluate (Plus expr0 expr1) = \\
 \ \ evaluate expr0 + evaluate expr1 \\
\color{white}. \\
test0 = evaluate (Literal 1) \\
test1 = evaluate (Plus (Literal 1) (Literal 2)) \\
test2 = evaluate (Plus (Plus (Literal 1) \\
 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (Literal 2)) \\
 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (Literal 3))
}

\frame{\frametitle{First Expression and evaluate (\jref{https://github.com/godfat/sandbox/blob/master/haskell/fpug/01/00.lhs
}{source})}
\footnotesize
\usebeamerfont*{font DejaVu Sans Mono}
module Main where \\
{\color{white}.} \\
data Expression = Literal Integer \\
 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ | Plus Expression Expression \\
{\color{white}.} \\
evaluate :: Expression -> Integer \\
evaluate (Literal i) \ \ \ \ \ \ \ = i \\
evaluate (Plus expr0 expr1) = \\
 \ \ evaluate expr0 + evaluate expr1 \\
{\color{white}.} \\
test0 = evaluate (Literal 1) \\
test1 = evaluate (Plus (Literal 1) (Literal 2)) \\
test2 = evaluate (Plus (Plus (Literal 1) \\
 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (Literal 2)) \\
 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (Literal 3))
}

\frame{\frametitle{Algebraic Datatypes}
\footnotesize
\usebeamerfont*{font DejaVu Sans Mono}
{\color{white} module Main where \\
.} \\
data Expression = Literal Integer \\
 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ | Plus Expression Expression \\
{\color{white}. \\
evaluate :: Expression -> Integer \\
evaluate (Literal i) \ \ \ \ \ \ \ = i \\
evaluate (Plus expr0 expr1) = \\}
\usebeamerfont*{font DejaVu Sans} {\color{darkblue} Think of interface and subclasses if you like OOP} \\
\usebeamerfont*{font DejaVu Sans Mono} \color{white} . \\
test0 = evaluate (Literal 1) \\
test1 = evaluate (Plus (Literal 1) (Literal 2)) \\
test2 = evaluate (Plus (Plus (Literal 1) \\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (Literal 2)) \\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (Literal 3))
}

\frame{\frametitle{Pattern Matching}
\footnotesize
\usebeamerfont*{font DejaVu Sans Mono}
{\color{white} module Main where \\
.} \\
data Expression = Literal Integer \\
 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ | Plus Expression Expression \\
{\color{white}.} \\
evaluate :: Expression -> Integer \\
evaluate (Literal i) \ \ \ \ \ \ \ = i \\
evaluate (Plus expr0 expr1) = \\
 \ \ evaluate expr0 + evaluate expr1 \\
{\color{white}. \\
test0 = evaluate (Literal 1)} \\
\usebeamerfont*{font DejaVu Sans} {\color{darkblue} Think of dynamic\raisebox{.5mm}{\underline{ }}cast or instanceof with a switch if you like OOP} \\
\usebeamerfont*{font DejaVu Sans Mono} \color{white} test2 = evaluate (Plus (Plus (Literal 1) \\
 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (Literal 2)) \\
 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (Literal 3))
}

\frame{\frametitle{First Expression and evaluate (\jref{https://github.com/godfat/sandbox/blob/master/haskell/fpug/01/00.lhs
}{source})}
\footnotesize
\usebeamerfont*{font DejaVu Sans Mono}
module Main where \\
{\color{white}.} \\
data Expression = Literal Integer \\
 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ | Plus Expression Expression \\
{\color{white}.} \\
evaluate :: Expression -> Integer \\
evaluate (Literal i) \ \ \ \ \ \ \ = i \\
evaluate (Plus expr0 expr1) = \\
 \ \ evaluate expr0 + evaluate expr1 \\
{\color{white}.} \\
test0 = evaluate (Literal 1) \\
test1 = evaluate (Plus (Literal 1) (Literal 2)) \\
test2 = evaluate (Plus (Plus (Literal 1) \\
 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (Literal 2)) \\
 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (Literal 3))
}

\frame{\frametitle{Variable and Environment (\jref{https://github.com/godfat/sandbox/blob/master/haskell/fpug/01/01.lhs
}{source})}
\vskip -2.6mm%
\footnotesize
\usebeamerfont*{font DejaVu Sans Mono}
module Main where \\
{\color{white}.} \\
data Expression = Literal Integer \\
 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ | Plus Expression Expression \\
 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ | Variable String \\
\color{white}. \\
type Environment = [(String, Integer)] \\
\color{white}. \\
evaluate :: Expression -> Environment -> Integer \\
evaluate (Literal i) \ \ \ \ \ \ \ env = i \\
evaluate (Plus expr0 expr1) env = \\
 \ \ evaluate expr0 env + evaluate expr1 env \\
evaluate (Variable name) \ \ \ env = \\
 \ \ case lookup name env of (Just i) -> i
}

\frame{\frametitle{Variable and Environment (\jref{https://github.com/godfat/sandbox/blob/master/haskell/fpug/01/01.lhs
}{source})}
\vskip -2.6mm%
\footnotesize
\usebeamerfont*{font DejaVu Sans Mono}
module Main where \\
{\color{white}.} \\
data Expression = Literal Integer \\
 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ | Plus Expression Expression \\
 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ | Variable String \\
{\color{white}.} \\
type Environment = [(String, Integer)] \\
\color{white}. \\
evaluate :: Expression -> Environment -> Integer \\
evaluate (Literal i) \ \ \ \ \ \ \ env = i \\
evaluate (Plus expr0 expr1) env = \\
 \ \ evaluate expr0 env + evaluate expr1 env \\
evaluate (Variable name) \ \ \ env = \\
 \ \ case lookup name env of (Just i) -> i
}

\frame{\frametitle{Variable and Environment (\jref{https://github.com/godfat/sandbox/blob/master/haskell/fpug/01/01.lhs
}{source})}
\vskip -2.6mm%
\footnotesize
\usebeamerfont*{font DejaVu Sans Mono}
module Main where \\
{\color{white}.} \\
data Expression = Literal Integer \\
 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ | Plus Expression Expression \\
 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ | Variable String \\
{\color{white}.} \\
type Environment = [(String, Integer)] \\
{\color{white}.} \\
evaluate :: Expression -> Environment -> Integer \\
\color{white} evaluate (Literal i) \ \ \ \ \ \ \ env = i \\
evaluate (Plus expr0 expr1) env = \\
 \ \ evaluate expr0 env + evaluate expr1 env \\
evaluate (Variable name) \ \ \ env = \\
 \ \ case lookup name env of (Just i) -> i
}

\frame{\frametitle{Variable and Environment (\jref{https://github.com/godfat/sandbox/blob/master/haskell/fpug/01/01.lhs
}{source})}
\vskip -2.6mm%
\footnotesize
\usebeamerfont*{font DejaVu Sans Mono}
module Main where \\
{\color{white}.} \\
data Expression = Literal Integer \\
 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ | Plus Expression Expression \\
 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ | Variable String \\
{\color{white}.} \\
type Environment = [(String, Integer)] \\
{\color{white}.} \\
evaluate :: Expression -> Environment -> Integer \\
evaluate (Literal i) \ \ \ \ \ \ \ env = i \\
evaluate (Plus expr0 expr1) env = \\
 \ \ evaluate expr0 env + evaluate expr1 env \\
evaluate (Variable name) \ \ \ env = \\
 \ \ case lookup name env of (Just i) -> i
}

\frame{\frametitle{Variable and Environment (\jref{https://github.com/godfat/sandbox/blob/master/haskell/fpug/01/01.lhs
}{source})}
\vskip -2.6mm%
\footnotesize
\usebeamerfont*{font DejaVu Sans Mono}
test0 = evaluate (Variable "var") [("var", 1)] \\
test1 = evaluate (Plus (Variable "var") (Literal 2)) [("var", 1)]
}

\frame{\frametitle{Type Alias}
\vskip -2.6mm%
\footnotesize
\usebeamerfont*{font DejaVu Sans Mono}
module Main where \\
{\color{white}.} \\
data Expression = Literal Integer \\
 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ | Plus Expression Expression \\
 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ | Variable {\color{darkblue}Name} \\
{\color{white}.} \\
type {\color{darkblue}Name} = String \\
type Environment = [({\color{darkblue}Name}, Integer)] \\
{\color{white}.} \\
evaluate :: Expression -> Environment -> Integer \\
evaluate (Literal i) \ \ \ \ \ \ \ env = i \\
evaluate (Plus expr0 expr1) env = \\
 \ \ evaluate expr0 env + evaluate expr1 env \\
evaluate (Variable name) \ \ \ env = \\
 \ \ case lookup name env of (Just i) -> i
}
\frame{\frametitle{Pair of a and b}
\vskip -2.6mm%
\footnotesize
\usebeamerfont*{font DejaVu Sans Mono}
("var", 2) :: (String, Integer) \\
(2, "var") :: (Integer, String)
}

\frame{\frametitle{List of a}
\vskip -2.6mm%
\footnotesize
\usebeamerfont*{font DejaVu Sans Mono}
$\begin{array}{l}
\text{[1,2,3] :: [Integer]} \\
\text{["a","b","c"] :: [String]} \\
\text{[("var", 1)] :: [(String, Integer)]}
\end{array}$
}

\frame{\frametitle{Curried Functions}
\vskip -2.6mm%
\footnotesize
\usebeamerfont*{font DejaVu Sans Mono}
evaluate :: Expression -> Environment -> Integer
}

\frame{\frametitle{Curried Functions}
\vskip -2.6mm%
\footnotesize
\usebeamerfont*{font DejaVu Sans Mono}
evaluate :: Expression -> (Environment -> Integer)
}

\frame{\frametitle{Uncurried Functions}
\vskip -2.6mm%
\footnotesize
\usebeamerfont*{font DejaVu Sans Mono}
evaluate :: (Expression, Environment) -> Integer
}

\frame{\frametitle{Uncurried Functions}
\vskip -2.6mm%
\footnotesize
\usebeamerfont*{font DejaVu Sans Mono}
threeArguments :: \\ (String, String, String) -> Integer
}

\frame{\frametitle{Curried Function}
\vskip -2.6mm%
\footnotesize
\usebeamerfont*{font DejaVu Sans Mono}
threeArguments :: \\ String -> String -> String -> Integer
}

\frame{\frametitle{Curried Function}
\vskip -2.6mm%
\footnotesize
\usebeamerfont*{font DejaVu Sans Mono}
threeArguments :: \\ String -> (String -> String -> Integer)
}

\frame{\frametitle{Curried Function}
\vskip -2.6mm%
\footnotesize
\usebeamerfont*{font DejaVu Sans Mono}
threeArguments :: \\ String -> (String -> (String -> Integer))
}

\ftc{(->) is right-associative}

\frame{\frametitle{Partially Applied Function}
\vskip -2.6mm%
\footnotesize
\usebeamerfont*{font DejaVu Sans Mono}
filter :: (a -> Bool) -> [a] -> [a] \\
{\color{white}.} \\
above60 :: [a] -> [a] \\
above60 = filter (>=60) \\
{\color{white}.} \\
above60 [1..65] -- [60,61,62,63,64,65]
}

\frame{\frametitle{Partially Applied Function}
\vskip -2.6mm%
\footnotesize
\usebeamerfont*{font DejaVu Sans Mono}
map :: (a -> b) -> [a] -> [b] \\
{\color{white}.} \\
div2 :: [Integer] -> [Integer] \\
div2 = map (`div`2) \\
{\color{white}.} \\
div2 [1..5] -- [0,1,1,2,2]
}

\frame{\frametitle{Function Composition}
\vskip -2.6mm%
\footnotesize
\usebeamerfont*{font DejaVu Sans Mono}
(.) :: (b -> c) -> (a -> b) -> a -> c \\
{\color{white}.} \\
above60AndDiv2 :: [Integer] -> [Integer] \\
above60AndDiv2 = div2 . above60 \\
{\color{white}.} \\
above60AndDiv2 [1..65] -- [30,30,31,31,32,32]
}

\frame{\frametitle{Function Composition}
\vskip -2.6mm%
\footnotesize
\usebeamerfont*{font DejaVu Sans Mono}
compose :: (b -> c) -> (a -> b) -> a -> c \\
compose g f x = g (f x) \\
}

\frame{
\vskip -2.6mm%
\usebeamerfont*{font DejaVu Sans}
Curried functions make function composition powerful, \\
function composition makes curried function even more useful.
}

\frame{\frametitle{List of Partially Applied Functions}
\vskip -2.6mm%
\footnotesize
\usebeamerfont*{font DejaVu Sans Mono}
mapPlus = map (+) -- think of [(+), (+), ...] \\
{\color{white}.} \\
mapPlus1to5 = mapPlus [1..5] \\
-- think of [(1+), (2+), ...] \\
{\color{white}.} \\
map (\$1) mapPlus1to5 -- [2,3,4,5,6] \\
{\color{white}.} \\
{\color{white}.} \\
-- applicative functor style \\
(+) <\$> [1..5] <*> [1] -- [2,3,4,5,6]
}

\frame{\frametitle{Exception Handling}
\vskip -2.6mm%
\footnotesize
\usebeamerfont*{font DejaVu Sans Mono}
data Expression = Literal Integer \\
 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ | Plus Expression Expression \\
 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ | Variable Name \\
{\color{white}.} \\
type Name = String \\
type Environment = [(Name, Integer)] \\
{\color{white}.} \\
type {\color{darkblue}Value} = Maybe Integer \\
{\color{white}.} \\
evaluate :: Expression -> Environment -> {\color{darkblue}Value} \\
}

\frame{\frametitle{Exception Handling}
\vskip -2.6mm%
\footnotesize
\usebeamerfont*{font DejaVu Sans Mono}
data Expression = Literal Integer \\
 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ | Plus Expression Expression \\
 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ | Variable Name \\
{\color{white}.} \\
type Name = String \\
type Environment = [(Name, Integer)] \\
{\color{white}.} \\
type {\color{darkblue}Value} = Maybe Integer \\
{\color{white}.} \\
evaluate :: Expression -> Environment -> {\color{darkblue}Value} \\
evaluate (Literal i) \ \ \ \ \ \ \ env = Just i \\
evaluate (Variable name) \ \ \ env = lookup name env
}

\frame{\frametitle{Exception Handling}
\vskip -2.6mm%
\footnotesize
\usebeamerfont*{font DejaVu Sans Mono}
evaluate (Plus expr0 expr1) env = \\
 \ \ let val0 = evaluate expr0 env \\
 \ \ \ \ \ \ val1 = evaluate expr1 env \\
 \ \ in \\
 \ \ \ \ \ \ case val0 of \\
 \ \ \ \ \ \ \ \ (Nothing) -> Nothing \\
 \ \ \ \ \ \ \ \ (Just i0) -> case val1 of \\
 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (Nothing) -> Nothing \\
 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (Just i1) -> Just (i0 + i1)
}

\frame{\frametitle{Maybe Monad with do notation}
\vskip -2.6mm%
\footnotesize
\usebeamerfont*{font DejaVu Sans Mono}
evaluate (Plus expr0 expr1) env = \\
 \ \ do \\
 \ \ \ \ val0 <- evaluate expr0 env \\
 \ \ \ \ val1 <- evaluate expr1 env \\
 \ \ \ \ return (val0 + val1)
}

\frame{\frametitle{Do notation underneath}
\vskip -2.6mm%
\footnotesize
\usebeamerfont*{font DejaVu Sans Mono}
evaluate (Plus expr0 expr1) env = \\
 \ \ evaluate expr0 env >>= \textbackslash val0 -> \\
 \ \ \ \ evaluate expr1 env >>= \textbackslash val1 -> return (val0 + val1)
}

\frame{\frametitle{liftM2}
\vskip -2.6mm%
\footnotesize
\usebeamerfont*{font DejaVu Sans Mono}
evaluate (Plus expr0 expr1) env = \\
 \ \ evaluate expr0 env `plus` evaluate expr1 env where \\
 \ \ plus = liftM2 (+)
}

\ftc{Sorry! To be continued...}

\frame{\frametitle{Peek the final work}
\jref{https://github.com/godfat/sandbox/blob/master/haskell/fpug/01/last.hs}{https://github.com/godfat/sandbox/blob/master/haskell/fpug/01/last.hs}
}
