AnInvitationToHaskell.tex

\documentclass[tikz]{beamer}


\usepackage{minted}
%\usepackage[parfill]{parskip}    		
\usepackage{graphicx}				
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{bm}
\usepackage{tikz-cd}
\usepackage{enumerate}
\usepackage{xfrac}
\usepackage{hyperref}
\usepackage{graphicx} \graphicspath{ {./} }
\usepackage{xcolor}
\usepackage{bbold}


\newcommand{\cat}[1]{\bm{ \mathsf{#1} }}
\newcommand{\functor}[3]{#1 : \cat{#2} \to \cat{#3}}
\newcommand{\functordef}{\functor{F}{C}{D}}
\newcommand{\cc}{\cat{C}}
\newcommand{\dd}{\cat{D}}
\newcommand{\ee}{\cat{E}}
\newcommand{\subcat}[2]{\bm{ \mathsf{#1}}_{\bm{ \mathsf{#2}}}}
\newcommand{\op}[1]{#1^{\text{op}}}
\newcommand{\opc}{\op{\cc}}
\newcommand{\opd}{\op{\dd}}
\newcommand{\ope}{\op{\ee}}
\newcommand{\mono}{\rightarrowtail}
\newcommand{\epi}{\twoheadrightarrow}
\newcommand{\zero}{\bm{\mathbb{0}}}
\newcommand{\one}{\bm{\mathbb{1}}}
\newcommand{\two}{\bm{\mathbb{2}}}
\newcommand{\three}{\bm{\mathbb{3}}}
\newcommand{\bg}{\cat{BG}}
\newcommand{\bgg}{\cat{BG'}}
\newcommand{\nt}{\Rightarrow}
\newcommand{\ant}[2]{\alpha : F \nt G} 
\newcommand{\bnt}[2]{\beta : F \nt G} 
\newcommand{\anti}[2]{\alpha : F \cong G} 
\newcommand{\bnti}[2]{\beta : F \cong G} 
\newcommand{\red}[1]{\textcolor{red}{#1}}
\newcommand{\mred}[1]{\textcolor{red}{$#1$}}
\newcommand{\blue}[1]{\textcolor{blue}{#1}}
\newcommand{\mblue}[1]{\textcolor{blue}{$#1$}}

% \newcommand{\haskell}[1]{\begin{minted}{haskell}#1\end{minted}}

\setbeamertemplate{navigation symbols}{\insertframenumber{}}
\colorlet{shadecolor}{gray!15}
\usepackage[utf8]{inputenc}
\usepackage[english]{babel}
\newcommand{\propnumber}{} % initialize
\newtheorem*{prop}{Proposition \propnumber}
\theoremstyle{definition}
\newtheorem{defn}{Definition}[section]

\AtBeginSection[]{
  \begin{frame}
        \frametitle{Table of Contents}
        \tableofcontents[currentsection]
  \end{frame}
}

\AtBeginSubsection[]
{
    \begin{frame}
        \frametitle{Table of Contents}
        \tableofcontents[currentsection,currentsubsection]
    \end{frame}
}

\title{An Invitation to Haskell}
\author{Emily Pillmore}

\begin{document}

\frame{\titlepage}


% \frame{\tableofcontents[hideallsubsections]}
 
\section{Introduction}

\frame
{
	My name is Emily Pillmore.
	
	I am a programmer, and a math enthusiast. 
}

\frame
{
	\begin{itemize}
		\item Author/Maintainer of more than 30 packages, some bigger than others
		\item Served on the Haskell Core Libraries and .Org committees
		\item Twitter (\blue{\href{https://twitter.com/yandereidiot}{@yandereidiot}})
		\item Meetups in NYC: NY Homotopy Type Theory, NY Category Theory, and the NY Haskell User Group. 
		\item All of my slides, general scribbles, research, and meetup content are hosted at \blue{\href{https://github.com/cohomolo-gy}{cohomolo.gy}}.
	\end{itemize}
	
	
	If you ever want to talk math or programming, I'm around.
}

\frame
{
	\begin{center}
		I helped start the \blue{\href{https://haskell.foundation}{Haskell Foundation}} and served on the executive leadership team as a duo (CTO) with Andrew Boardman (ED).  \\
		\includegraphics[scale=0.3]{haskell-foundation}
	\end{center}
}

\frame
{ 

	\begin{center}
	I now work at a company called \textbf{Kadena}, as the lead of the language, its ecosystem, and its execution layers. \\
		\includegraphics[scale=0.3]{kadena}
	\end{center}
	
}

\section{Functional Programming}

\frame {
So what is Functional Programming? 

}

\frame {
So what is Functional Programming? 

\begin{center}
	\begin{itemize}
		\item A collection of features? (lambdas, first class HOF's, static type system...)
	\end{itemize}
\end{center}

}

\frame {
So what is Functional Programming? 

\begin{center}
	\begin{itemize}
		\item A collection of features? (lambdas, first class HOF's, static type system...)
		\item A programming style? (emphasis on recursion, "math", small static combinators, shunting as many errors to the compiler as possible)
	\end{itemize}
\end{center}

}

\frame {
So what is Functional Programming? 

\begin{center}
	\begin{itemize}
		\item A collection of features? (lambdas, first class HOF's, static type system...)
		\item A programming style? (emphasis on recursion, "math", small static combinators, shunting as many errors to the compiler as possible)
		\item A cult?
	\end{itemize}
\end{center}

}

\subsection{Foundations}
\frame{
	In 1977, John Backus wrote \blue{\href{http://worrydream.com/refs/Backus-CanProgrammingBeLiberated.pdf}{everything we needed to know about FP}}. 
}

\frame{
	Compositionality! Equational Reasoning! Sound foundational principles!
}

\subsection{Purity}

\frame{
	Haskell builds a equational foundation on \red{purity}.
}

\frame{
	This means that functions may not have \textit{side effects}. In conjunction with not allowing side effects anywhere, this allows expressions to be completely deterministic, and therefore they are \textit{referentially transparent}.
}

\subsection{Types}

\frame{
	Famously, Haskell has a type system.
}

\frame{
	Famously, Haskell has a type system.
	
	\begin{itemize}
		\item It has functions (read: function definitions, lambdas)
	\end{itemize}
}

\frame{
	Famously, Haskell has a type system.
	
	\begin{itemize}
		\item It has functions (read: function definitions, lambdas)
		\item It has builtins (integers, IEEE floating points, machine words, characters etc.)
	\end{itemize}
}

\frame{
	Famously, Haskell has a type system.
	
	\begin{itemize}
		\item It has functions (read: function definitions, lambdas)
		\item It has builtins (integers, IEEE floating points, machine words, characters etc.)
		\item It has generics
	\end{itemize}
}

\frame{
	Haskell has a global notion of parametricity everywhere you want it which may be reasoned about equationally, and therefore free theorems you can reason about.
}

\frame{
	It has a form of ad-hoc polymorphism for generics called "Typeclasses".
}

\frame{
	For more, see: 
	
		\begin{itemize}
			\item Wadler - \blue{\href{https://dl.acm.org/doi/pdf/10.1145/99370.99404}{Theorems for Free}}
			\item My talk - \blue{\href{https://github.com/cohomolo-gy/Type-Arithmetic-and-the-Yoneda-Perspective/blob/master/typearithmeticyl.pdf}{Type Arithmetic}}
		\end{itemize}
}

\subsection{Consequences}
	
\frame{
	Since purity undermines destructive updates, our Haskell data structures are immutable. This creates some issues.
	
}

\frame{
	Since purity undermines destructive updates, our Haskell data structures are immutable. This creates some issues.
	
	\begin{itemize}
		\item The amortized complexity theory needed to talk about the best/average/worst case of operations goes out the window (your average case becomes your worst case for many operations). 
	\end{itemize}
	
}

\frame{
	Since purity undermines destructive updates, our Haskell data structures are immutable. This creates some issues.
	
	\begin{itemize}
		\item The amortized analysis (cheap small steps paying off a more expensive larger step) needed to talk about the best/average/worst case of operations goes out the window (your amortized cost becomes your worst case for many operations). 
		\item Laziness (a limited form of mutation) turns out to be enough to recover amortized analysis 
	\end{itemize}
	
}

\frame{
	Since purity undermines destructive updates, our Haskell data structures are immutable. This creates some issues.
	
	\begin{itemize}
		\item The amortized analysis (cheap small steps paying off a more expensive larger step) needed to talk about the best/average/worst case of operations goes out the window (your amortized cost becomes your worst case for many operations). 
		\item Laziness (a limited form of mutation) turns out to be enough to recover amortized analysis.
		\item This requires a different take on analysis (thunk counting techniques etc.) which causes you to think in a whole new paradigm. 
	\end{itemize}
	
}

\frame{
	Since purity undermines destructive updates, our Haskell data structures are immutable. This creates some issues.
	
	\begin{itemize}
		\item The amortized analysis (cheap small steps paying off a more expensive larger step) needed to talk about the best/average/worst case of operations goes out the window (your amortized cost becomes your worst case for many operations). 
		\item Laziness (a limited form of mutation) turns out to be enough to recover amortized analysis.
		\item This requires a different take on analysis (thunk counting techniques etc.) which causes some tension.
	\end{itemize}
	
}

\frame{
	Immutability + Laziness, though, is a super power. \blue{\href{https://legacy.cs.indiana.edu/ftp/techreports/TR44.pdf}{Friedman-Wise}} posed an important question back in 1976.
}

\frame{
	Inherently easy to spread about on multiple cores. With commutative, associative, and unital (see: commutative monoidal) functions, map-reduce is possible. 
}

\frame{
	It also makes scheduling parallelism and concurrency a simpler. 
}

\section{Examples}

\subsection{Basics}

\frame{ 
	In haskell, we write the definition for functions and constants like this:
}

\begin{frame}[fragile]
	In haskell, we write the definition for functions and constants like this:
	
	\begin{minted}{haskell}
		-- a function
		square :: Int -> Int 
		square x = x ^ x	
	\end{minted}
\end{frame}

\begin{frame}[fragile]
	In haskell, we write the definition for functions and constants like this:
	
	\begin{minted}{haskell}
	-- a function
	square :: Int -> Int -- a type signature
	square x = x ^ x	
	
	-- Constants
	pi_trunc :: Double
	pi_trunc = 3.14159265359
		
	charizard :: Char
	charizard = 'c'
		
	stringy :: String
	stringy = "Hi, SEMIBUG!"
		
	\end{minted}
\end{frame}

\begin{frame}[fragile]
	In haskell, we write the definition for functions and constants like this:
	
	\begin{minted}{haskell}
	-- builtin lists
	oneTwoThree :: [Int]
	oneTwoThree = [1,2,3]
	
	-- builtin tuples
	ab :: a -> b -> (a,b)
	ab a b = (a,b) 
		
	\end{minted}
\end{frame}

\begin{frame}[fragile]
	One can also define functions of multiple inputs like so: 
\end{frame}

\begin{frame}[fragile]
	One can also define functions of multiple inputs like so: 
	
	\begin{minted}{haskell}
	plus :: Int -> Int -> Int 
	plus x y = x + y
		
	-- Int -> Int -> Int is the 
	-- same as Int -> (Int -> Int)
	plus' :: Int -> Int -> Int 
	plus' x = \y -> x + y	
	\end{minted}
	
\end{frame}

\begin{frame}[fragile]
	Function types are defined syntactically by enclosing parens 
\end{frame}

\begin{frame}[fragile]
	Function types are defined syntactically by enclosing parens 

\begin{center}
	\begin{minted}{haskell}
	apply :: (a -> b) -> a -> b
	-- apply = id
	apply f a = f a
	
	compose 
	  :: (b -> c)
	  -> (a -> b)
	  -> (a -> c)
	compose f g = \a -> f (g a)
	\end{minted}
	\end{center}
\end{frame}

\begin{frame}[fragile]
Defining infix notation is easy as well (not pictured: fixity): 

\begin{center}
	\begin{minted}{haskell}
	(^+) :: Int -> Int -> Int
	(^+) x y = x + y
	-- usage: x ^+ y
	\end{minted}
\end{center}
\end{frame}

\subsection{Data}
\begin{frame}[fragile]

We can define data as follows: 

\begin{center}
	\begin{minted}{haskell}
	-- data DataType <tyvars>
	--   = Case1 
	--   | Case2
	--   | ...
	data MyAdt = Thing1 | Thing2 
	
	data MyRec = MyRecordName
	  { foo :: Int 
	    -- ^ foo :: MyRecordName -> Int
	  , bar :: String
	    -- ^ bar :: MyRecordName -> String
	  }	  	  
	\end{minted}
\end{center}

\end{frame}

\begin{frame}[fragile]
\begin{center}
	\begin{minted}{haskell}
	-- data DataType <tyvars>
	--   = Case1 
	--   | Case2
	--   | ...
	data MyAdt = Thing1 | Thing2 
	
	data MyRec = MyRecordName
	  { foo :: Int 
	    -- ^ foo :: MyRecordName -> Int
	  , bar :: String
	    -- ^ bar :: MyRecordName -> String
	  }  
	\end{minted}
\end{center}
\end{frame}

\begin{frame}[fragile]

Pattern matching is the means by which one destructs sum types.
\begin{center}
	\begin{minted}{haskell}
	let 
	  x :: MyDataType
	  x = Case1
			
	in case x of 
	  Case1 -> "hi!"
	  Case2 -> "Death!"  
	\end{minted}
\end{center}
\end{frame}

\subsection{Folds}

\frame{
As mentioned in the beginning of the talk, immutable data structures let us achieve some remarkable properties. 
}

\frame{
	We can write recursive data definitions for things like Lists: 
	
}

\begin{frame}[fragile]
	We can write recursive data definitions for things like Lists: 

\begin{center}
	\begin{minted}{haskell}
	data List a = Nil | Cons a (List a)
	-- builtin: data [a] = [] | (:) a [a]
	-- usage: Cons 1 (Cons 2 (Cons 3 Nil))
	-- usage: [1,2,3] := 1:(2:(3:[])) 
	\end{minted}
\end{center}
\end{frame}

\begin{frame}[fragile]
	Noodle baker: why does this work?
	
	\begin{center}
	\begin{minted}{haskell}
	-- List(a) = 1 + a * List(a)
	-- List(a) - a*List(a) = 1
	-- List(a)(1 - a) = 1
	-- List(a) = 1 / (1 - a)
	-- List(a) = 1 + a + a^2 + a^3 ...
	\end{minted}
	\end{center}
\end{frame}

\begin{frame}[fragile]
\begin{center}
	\begin{minted}{haskell}
	reduce :: (a -> b -> b) -> b -> [a] -> b
	reduce step accum lst = case lst of 
	  [] -> accum 
	  first:rest -> 
	    let stepped = step first accum
	    in reduce step stepped rest
	\end{minted}
\end{center}

\end{frame}

\frame { 
	\textit{reduce} is commonly referred to as a "fold". In fact, 
	it's a \textit{"right fold"} in the sense that the values are accumulated thusly: 
}

\begin{frame}[fragile] 
	\textit{reduce} is commonly referred to as a "fold". In fact, 
	it's a \textit{"right fold"} in the sense that the values are accumulated thusly:
	
	\begin{center}
		\begin{minted}{haskell}
		reduce (+) 0 [1,2,3]
		-- ~ reduce (+) 0 (1:(2:(3:[])))
		-- ~ 1 + reduce (+) 0 (2:(3:[]))
		-- ~ 1 + (2 + (reduce (+) 0 (3:[])))
		-- ~ 1 + (2 + (3 + reduce (+) 0 []))
		-- ~ 1 + (2 + (3 + 0))
		-- ~ 1 + (2 + 3)
		-- ~ 1 + 5
		-- ~ 6
		\end{minted}
	\end{center}
\end{frame}


\frame { 
	Claim: this function corresponds with a kind of "canonical way to reduce a list recursively". As a result, one may define many interesting properties of a list in terms of this formulation. 
}

\begin{frame}[fragile]
	\begin{center}
		\begin{minted}{haskell}
	sum :: [Int] -> Int
	sum lst = reduce (+) 0 lst 
		
	product :: [Int] -> Int
	product lst = reduce (*) 1 lst
		
	filter :: (a -> Bool) -> [a] -> [a]
	filter p lst = reduce 
	  (\a acc -> if p a then a:acc else acc)
	  [] lst
		
	map :: (a -> b) -> [a] -> [b]
	map f lst = reduce
	 (\a acc -> (f a):acc) [] lst
	\end{minted}
	\end{center}
\end{frame}

\begin{frame}[fragile]
	\begin{center}
		\begin{minted}{haskell}
	-- data Bool = True | False
	all :: [Bool] -> Bool
	all bs = reduce (&&) True bs
		
	any :: [Bool] -> Bool
	any bs = reduce (||) False bs
		\end{minted}
	\end{center}
\end{frame}

\frame{
	Graham Hutton's paper \blue{\href{https://www.cs.nott.ac.uk/~pszgmh/fold.pdf}{A tutorial on the universality and expressiveness of fold}} is a great resource on the subject.
}

\frame{
	These are definable in any language for any list. But in haskell, with the right foundation, they're understandable one-liners. 
}

\frame{
	Further, we have laziness. This implies a thing called \textit{shortcircuiting}. 
}

\frame{
	Typeclasses are a means of layering ad-hoc behaviors. 
}

\begin{frame}[fragile]
\begin{center}
	\begin{minted}{haskell}
	class Functor (f :: Type -> Type) where 
	  fmap :: (a -> b) -> f a -> f b
	  
	instance Functor List where 
	  -- fmap :: (a -> b) -> List a -> List b
	  fmap f Nil = Nil
	  fmap f (Cons h t) = Cons (f h) (fmap f h)
	\end{minted}
\end{center}
\end{frame}

\begin{frame}[fragile]
\begin{center}
	\begin{minted}{haskell}
	functorFloor :: Functor f => f Double -> f Int
	functorFloor dubs = fmap floor dubs
	
	-- class Show a where show :: a -> String
	stringify :: [Int] -> [String]
	stringify = fmap show
	\end{minted}
\end{center}
\end{frame}

\begin{frame}[fragile]
\begin{center}
	\begin{minted}{haskell}
	
	-- instances: 
	-- Int, <> = +, <> = *, etc.
	class Semigroup a where 
	  (<>) :: a -> a -> a
	  
	-- instances: 
	-- Int, unit = 0, unit = 1
	class Semigroup a => Monoid a where 
	  unit :: a
	\end{minted}
\end{center}
\end{frame}


\section{Building Stuff}

\subsection{Ghcup}

\frame{
	You can get everything you need from a tool called "ghcup".
}

\frame{
	GHCup is the canonical toolchain installer. It will install the LSP, the compiler, and the build tools. 
}

\frame{
	Get it here: \blue{\href{https://get-ghcup.haskell.org}{get-ghcup}}
}

\subsection{Cabal}
\frame{
	Cabal is the Haskell project structure spec (as well as other tools), and cabal-install is the tool we use to build Haskell projects. 
}

\frame{
	Useful commands: 
	
	\begin{itemize}
		\item init
		\item build
		\item repl
		\item test
		\item run
		\item publish
	\end{itemize}
}

\frame{
	Dependencies are located by default in a community service called "Hackage". Cabal-install knows how to talk to this service. 
}
\frame{
	Pragmatically, Haskell works like any other language: 
	
	
}

\frame{
	Pragmatically, Haskell works like any other language: 

	\begin{itemize}
		\item Define a main
\end{itemize}		
	
}

\frame{
	Pragmatically, Haskell works like any other language: 

\begin{itemize}
		\item Define a main
		\item Do stuff in sequence
\end{itemize}		
	
}

\frame{
	Pragmatically, Haskell works like any other language: 

\begin{itemize}
		\item Define a main
		\item Do stuff in sequence
		\item Exit
\end{itemize}		
	
}

\subsection{IO}
\frame{
	Without spending too much on the dreaded "m-word" (it's monad), we have a monad called "IO". 
}

\frame{
	IO is a means of sequencing real world state changes.
}

\frame{
	In fact, it is "just" a state monad, for the curious reader.
}

\begin{frame}[fragile]
\begin{center}
	\begin{minted}{haskell}
	main :: IO ()
	main = putStrLn "Hello, World!"
	\end{minted}
\end{center}
\end{frame}


\section{Conclusion}

\frame{
	We're out of time, but this is a teaser for you. 
}

\frame{
	Takeaways: 
}

\frame{
	Takeaways: 
	
	\begin{itemize}
		\item Laziness + Purity = Performance + Reasoning
		
	\end{itemize}
}

\frame{
	Takeaways: 
	
	\begin{itemize}
		\item Laziness + Purity = Performance + Reasoning
		\item Reasoning + Consistency = Laws
	\end{itemize}
}

\frame{
	Takeaways: 
	
	\begin{itemize}
		\item Laziness + Purity = Performance + Reasoning
		\item Reasoning + Consistency = Laws
		\item Laws + Types = Fewer Bugs
		
	\end{itemize}
}

\frame{
	Takeaways: 
	
	\begin{itemize}
		\item Laziness + Purity = Performance + Reasoning
		\item Reasoning + Consistency = Laws
		\item Laws + Types = Fewer Bugs
		\item Fewer Bugs = Less Stressful Programs
	\end{itemize}
}

\frame{
	Haskell: lose your hair \textit{before} you run the program.
}

\frame{
	...and then probably after too (it's still programming).
}

\end{document}