FunctionalAlgebra.tex

\documentclass{beamer}

% \usepackage{beamerthemesplit} // Activate for custom appearance

\usepackage{listings}
\usepackage{xcolor}
\lstnewenvironment{code}{\lstset{language=Haskell,basicstyle=\small}}{}
\lstnewenvironment{ccode}{\lstset{language=C,basicstyle=\small}}{}
\usepackage{minted}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\lstnewenvironment{rcode}{\lstset{language=Ruby,basicstyle=\small}}{}

\title{Functional Algebra for Middle School Students}
\author{Chad Brewbaker\\ DataCulture LLC}
\date{May 27, 2016}

\begin{document}

\frame{\titlepage}

%\section[Outline]{}
%\frame{\tableofcontents}

%

\begin{frame}[fragile]
How can we get functional programming into universal education?\newline
\newline
What language did we use before COBOL and ALGOL?\newline
\newline
How can we refactor on a napkin without an IDE?\newline
\newline
How can we prove our code is correct?

\end{frame}


\begin{frame}[fragile]
How can we easily get programming in the Jr. High curriculum?\newline
(Algebra)\newline
What language did we use before COBOL and ALGOL?\newline
(Algebra)\newline
How can we refactor on a napkin without an IDE?\newline
(Algebra)\newline
How can we prove our code is correct?\newline
(Algebra)
\end{frame}


\begin{frame}[fragile]
1) Ignore fancy terminology.\newline\newline
2) Use sums, products, and exponents.\newline\newline
3) Teach Jr. High Algebra instructors just enough about type signatures.  
\end{frame}


\begin{frame}[fragile]
The Haskell language\newline\newline
Looks like Algebra. \newline\newline
Easy to reason about. No rando database calls in a function without IO warning.\newline\newline
Maximum flexibility for abstract design.
\end{frame}

\begin{frame}[fragile]
The Ruby language\newline\newline
Lots of existing projects for kids.\newline\newline
Play-dough on top of C.\newline\newline
Maximum flexibility for human tinkering.
\end{frame}

\begin{frame}[fragile]
The C language\newline\newline
Loosely typed machine instructions.\newline\newline
Maximum flexibility for machines.
\end{frame}

\begin{frame}[fragile]
Function notation: Algebra, Haskell, C, Ruby\newline\newline

$f(\mathbb{Z},\mathbb{Z}) \rightarrow$ String
\begin{code} 
f :: (Int, Int) -> String
\end{code}
\begin{ccode} 
String f(int a, int b); 
\end{ccode}
\end{frame}


\begin{frame}[fragile]
Longform functions in Ruby
\begin{rcode}
def f(a,b)
  #function body
end 
\end{rcode}

Short form functions in Ruby
\begin{rcode}
f = ->(a,b){
   #function body
}
\end{rcode}
\end{frame}


\begin{frame}[fragile]
Sum: $A$ or $B$\newline\newline
$$A + B $$

\begin{code} 
data X = A | B
\end{code}

Sally's drink is either Coffee or Tea.
\begin{code}
type Drink = Coffee | Tea
\end{code}
\end{frame}

\begin{frame}[fragile]
Sum: $A$ or $B$\newline\newline
$$A + B $$

C has enumeration types
\begin{ccode} 
enum X { A, B };
\end{ccode}

Ruby has enumerable types
\begin{rcode} 
x = Set.new [a,b]
\end{rcode}

\end{frame}


\begin{frame}[fragile]
Product: $A$ and $B$\newline\newline
$$A \times B$$

Haskell has product types, also known as tuples
\begin{code}
type X = (A,B)
\end{code}

Sally's dinner consists of a fruit and a vegetable.
\begin{code}
type Dinner =  (Fruit, Vegetable)
\end{code}
\end{frame}

\begin{frame}[fragile]
Product: $A$ and $B$\newline\newline
$$A \times B$$
\newline\newline
C has structs.\newline\newline
\begin{ccode}
struct X{ A a; B b;};
\end{ccode}

\end{frame}

\begin{frame}[fragile]
Product: $A$ and $B$\newline\newline
$$A \times B$$

\newline\newline
Ruby has Array types.
\begin{rcode}
x = [a,b]
\end{rcode}
\newline\newline 
Ruby classes can be used as product types.
\begin{rcode}
class Product
  @a = A.new()
  @b = B.new() 
end
x = Product.new()
\end{rcode}

\end{frame}


\begin{frame}[fragile]
Exponential: From A to B\newline\newline
$$ B^{A} $$
$A$ is called the domain or input type. $B$ is called co-domain or return type.
\begin{code}
f :: A -> B
\end{code}

Sally chops a carrot.
\begin{code}
chop :: Carrot -> DicedCarrot
\end{code}

\end{frame}


%\begin{frame}[fragile]
%Exponential: $B^{A} $\newline\newline
%
%Example from JEG's RailsConf2016 talk
%\begin{ccode}
%Integer fib(Integer a){
%   if (a == 0 || a == 1) 
%        return 1;
%   return fib(a-1) + fib(a-2);
%}
%\end{ccode}

%What is the runtime of fib(n)?
%\end{frame}


%\begin{frame}[fragile]
%Exponential: $ B^{A} $\newline\newline

%Focus on this line
%\begin{ccode}
%      return fib(a-1) + fib(a-2);
%\end{ccode}

%How many branches? Bool\newline
%How deep is each branch? $\approx A$ 
%\begin{code}
%fibExecutionUnit :: A -> Bool
%\end{code}
%         $$O(2^{A})$$
%\end{frame}


\begin{frame}[fragile]
Terminology for simple values.\newline\newline
$\sqrt{-1}$ Undefined (Irrational)
\begin{ccode}
0 Void
1 Unit, also ()
2 Bool 
3 Tri
4 Quad
\end{ccode}
\end{frame}

\begin{frame}[fragile]
Constants are functions with the Unit as an argument.
$$\textcolor{red}{a} = a^{1} $$
\color{red}
\begin{code}
foo ::  A
\end{code}
\color{black}
\begin{code}
bar :: () -> A
\end{code}
\end{frame}


\begin{frame}[fragile]
Tuples vs tuple lookups\\
$$\textcolor{red}{a \times a} = a^2$$

\color{red}
\begin{code}
foo :: (A,A)
\end{code}
\color{black}
\begin{code}
bar:: Bool -> A
\end{code}
Interpret $bar$ as choice between left A and right A.

\end{frame}


%\begin{frame}[fragile]
%\begin{ccode}
%Int  ifThenElse(int x){
%if( x)
%   return 3;
%else
%   return 4;
%}
%\end{ccode}
%If statements are an inlined boolean function
%\begin{code}
%f :: Bool -> a
%f x = if x then 3 else 4
%\end{code}

%$(a)^2 = (a,a)$

%\end{frame}

% log  p->a  = p
%colog p->a = a


%\begin{frame}[fragile]
%Switch statements are???
%\end{frame}


\begin{frame}[fragile]
Void behaves like zero
$$\textcolor{red}{1}= a^{0}$$
\color{red}
\begin{code}
foo :: Unit
\end{code}
\color{black}
\begin{code}
bar:: Void -> A
\end{code}
$$\textcolor{red}{a\times0} = 0$$
\color{red}
\begin{code}
foo :: (A,Void)
\end{code}
\color{black}
\begin{code}
bar:: Void
\end{code}

\end{frame}

\begin{frame}[fragile]
Void behaves like zero

$$\textcolor{red}{a+0} = a$$
\color{red}
\begin{code}
foo :: A | Void
\end{code}
\color{black}
\begin{code}
bar:: A
\end{code}
\end{frame}




\begin{frame}[fragile]
Derivative(N) is removing one element from N
$$ \textcolor{red}{{d \over dx}(ax^{n}) }= a \times n \times x^{n-1}$$
\begin{code}
data N = M | 1
\end{code}
\color{red}
\begin{code}
foo::  derivitaveN( a, N -> x)
\end{code}
\color{black}
\begin{code}
bar:: (a, N, M -> X)
\end{code}
\end{frame}

\begin{frame}[fragile]
Curry. We can pass argument lists or chain functions.
$$ \textcolor{red}{(a^{m})^{n}} = a^{mn}$$

\color{red}
\begin{code}
curryFoo :: n -> (m -> a)
\end{code}
\color{black}
\begin{code}
curryBar :: (n,m) -> a
\end{code}
\end{frame}

\begin{frame}[fragile]
\inputminted{Ruby}{curry.rb}


\inputminted{text}{curry.out}
\end{frame}



\begin{frame}[fragile]
Co-curry. Multiple function calls or return a tuple.
$$ \textcolor{red}{a^{m}b^{m}} = (ab)^{m}$$

\color{red}
\begin{code}
cocurryFoo :: (m -> a, m -> b)
\end{code}
\color{black}
\begin{code}
cocurryBar :: m -> (a,b)
\end{code}
\end{frame}

\begin{frame}[fragile]
\inputminted{Ruby}{cocurry.rb}


\inputminted{text}{cocurry.out}
\end{frame}


\begin{frame}[fragile]
Splitting function inputs
$$\textcolor{red}{a^{m}a^{n} }= a^{m+n}$$
\begin{code}
data B = M | N
\end{code}
\color{red}
\begin{code}
foo :: (M -> a, N -> a)
\end{code}
\color{black}
\begin{code}
bar :: B -> a
\end{code}
\end{frame}

\begin{frame}[fragile]
\inputminted{Ruby}{inputSplit.rb}


\inputminted{text}{inputSplit.out}
\end{frame}


\begin{frame}[fragile]
Ignoring some input or shrinking function input 
$$\textcolor{red}{ a^{m} \div a^{n}} = a^{m-n}$$
\begin{code}
data M = B | N
\end{code}
\color{red}
\begin{code}
f :: (M -> a) remove (N -> a)
\end{code}
\color{black}
\begin{code}
f' :: B -> a
\end{code}
\end{frame}

\begin{frame}[fragile]
\inputminted{Ruby}{ignoreInput.rb}


\inputminted{text}{ignoreInput.out}
\end{frame}



\begin{frame}[fragile]
Suppressing some outputs or shrinking the output type
$$ \textcolor{red}{a^{m} \div b^{m} }= ({a \over b})^{m}$$
\begin{code}
data A = N | B
\end{code}
\color{red}
\begin{code}
f :: (m -> A) remove (m -> B)
\end{code}
\color{black}
\begin{code}
f':: m -> N
\end{code}
\end{frame}

%\begin{frame}[fragile]
%\inputminted{Ruby}{ignoreOutput.rb}

%\inputminted{text}{ignoreOutput.out}
%\end{frame}


\begin{frame}[fragile]
Fermat's Little Theorem\\
$ a^{n} - a$ is divisible by $n$ when $n$ is prime.
$$ a^{n} - a = n\times k$$
$$ \textcolor{red}{a^{n} }= n\times k + a$$
\color{red}
\begin{code}
foo :: N -> A
\end{code}
\color{black}
\begin{code}
bar :: (N, K) | A
\end{code}
This refactoring exists whenever $N$ is a prime size set.
\end{frame}

\begin{frame}[fragile]
Fermat's Last Theorem\\

$ \textcolor{red}{x^{n} + y^{n} }= z^{n} $ has no solutions for $n>2$.\newline
\color{red}
\begin{code}
foo :: (N -> X) | (N -> Y)
\end{code}
\color{black}
\begin{code}
bar :: (N ->Z)
\end{code}
foo $\neq$  bar when $N$ is greater than size two.
\end{frame}


\begin{frame}[fragile]
Binomial Theorem.  \\ Refactor between product of sums and sum of products.
$$(a+b)^{n} = \sum_{k=0}^{n}{n \choose k} a^{n-k}b^{k}$$

$$\textcolor{red}{(a+b)^{2}} = a^{2} + 2ab + b^{2}$$
\color{red}
\begin{code}
foo :: Bool -> (A | B)
\end{code}
\color{black}
\begin{code}
bar :: Bool -> A
      | (Bool, A, B)
      | Bool -> B 
baz :: (A,A) | ((A,B) | (B,A)) | (B,B)
     
\end{code}
\end{frame}

%\begin{frame}[fragile]
%Binomial Theorem\\
%$(a+b)^{3} = a^{3} + 3a^{2}b + 3ab^{2} + b^{3}$

%\begin{code}
%f :: Tri -> (A | B)
%f' ::  Tri -> A  
%       | (Tri, Bool -> A, B)  
%       | (Tri, A, Bool -> B)
%       | Tri -> B
%f'' :: (A,A,A) 
%       | ( (A,A,B) | (A,B,A) | (B,A,A) )
%       | ( (A,B,B) | (A,B,B) | (B,A,B) )
%       | (B,B,B)
%\end{code}

%\end{frame}

\begin{frame}[fragile]
Tips on how to read Algebra as a programmer.
\end{frame}

\begin{frame}[fragile]
All the functions from $N$ to $N$.
$${N^{N}}$$
\end{frame}

\begin{frame}[fragile]
All reorderings of $N$.
$$n! = n*(n-1)*...*2*1$$
\end{frame}


\begin{frame}[fragile]
Let's ignore some stuff that is type X.
$${1\over x}$$
\end{frame}

\begin{frame}[fragile]
Let's ignore reordering.
$${1\over n!}$$
\end{frame}

\begin{frame}[fragile]
I'm about to give a stream of things.
$$\sum$$
\end{frame}

\begin{frame}[fragile]
I've got an arbitrarily large tuple.
$$\prod$$
\end{frame}



\begin{frame}[fragile]
Moving forward.\newline\newline
Teach Jr. High Algebra teachers basic type signatures.\newline\newline
Functions are exponents. More practice problems on towers of exponents.\newline\newline 
``Abstract" algebra can be obtuse. Be descriptive with concrete examples. Less jargon.\newline\newline
My research project Endoscope. Inspect function structure. Don't rely on intuition.
\end{frame}


\begin{frame}[fragile]
BONUS SLIDES

\end{frame}

\begin{frame}
Binary tree.\newline\newline
Empty tree or a parent node and two children. \newline\newline
Tree  A = EmptyTree + (Parent A ,Left A, Right  A)\newline\newline
$T_{a} = 1+a{T_{a}}^{2} $\newline\newline
$a{T_{a}}^{2 } - T_{a}+ 1  = 0$\newline\newline
Solve with quadratic formula.\newline\newline
%$T_{a} = {1 - \sqrt {1 - 4a} \over 2a}$\newline
\end{frame}

\begin{frame}[fragile]
What the heck do we do with this? %\newline\newline
$$T_{a} = {1 - \sqrt {1 - 4a} \over 2a}$$

Wolfram Alpha, "Series [ [1 - Sqrt[1-4a]] / [2a] ] at 0"
$$1+a+2a^{2}+5a^{3} + 14a^{4} + 132a^{6}...$$
\begin{code}
data SixTree A = (Void,Void -> a)  | (Unit,Unit -> A) 
   | (Quint, Tri -> A) | (Fourteen, Quad -> A)
   | (OneThrityTwo, Hex -> A) 
\end{code}
\end{frame}

\begin{frame}[fragile]
Monads are foreign because we aren't used to Algebra with towers of exponents. $m$ is usually a container or operating system call.\newline\newline
%bind $$(mb)^{ ((mb)^{a})^{ma}} $$
Sequentially compose two items in the $m$ context. Pipe the return of the first into the second.\newline
$(>>=) = {m_b}^{ {m_b}^{a}m_a} $\newline\newline
Sequentially compose two items in the $m$ context. Do not pipe the output of the first to the second.\newline
$(>>) = {m_b}^{m_b m_a}$\newline\newline
Put $a$ in the $m$ context.\newline
return $= {m_a}^{a}$\newline\newline
\end{frame}


\begin{frame}[fragile]
\begin{code}
import System.Environment as SE
import System.Process as SP

printPath = SE.getExecutablePath >>= print
sentence = "say Two plus one equals three"
twoPlusOne = SP.system sentence 
           >> print (2+1)

saywhat :: String -> String
saywhat x = "say " ++  x
sayit x = SP.system $ saywhat x

sayExePath = SE.getExecutablePath
            >>= \x -> sayit x
\end{code}


\end{frame}


%\frame
%{
 % \frametitle{Features of the Beamer Class}
%
 % \begin{itemize}
  %\item<1-> Normal LaTeX class.
  %\item<2-> Easy overlays.
  %\item<3-> No external programs needed.      
  %\end{itemize}
%}
%\end{document}




\frame
{
  \frametitle{Bibliography}
  Haskell Curry(1934), ``Functionality in Combinatory Logic"\newline\newline
  Eric G Wagner(1986), ``Categories, Data Types, and Imperative Languages"\newline\newline
  Douglas McIlroy(1998), ``Power Series, Power Serious"\newline\newline
  Chris Taylor(2013), ``The Algebra of Algebraic Data Types"
}
\end{document}