\begin{code}
module Jan18 where
\end{code}
Learning objectives (planned):
\begin{itemize}
\item fold (generalize in later lectures)
\item lazyness
\item polymorphism
\end{itemize}
SUPER IMPORTANT: \textbf{The only thing you can do with a function is call it!}
Folding right and left.
Context: a list, a binary function ‘f’ and a starting value ‘s’.
\lstinline|l = [a1, a2, a3, …, an]|
\begin{enumerate}
\item fold-right: a1 `f` (a2 `f` (a3 `f` …. (an `f` s)))
\item fold-left: (((s `f` a1) `f` a2) … `f` an)
\end{enumerate}
\begin{code}
— foldr in Haskell
fold_right :: (a -> b -> b) -> b -> [a] -> b
fold_right f s [] = s
fold_right f s (x:xs) = x `f` (fold_right f s xs)
\end{code}
We tried:
\begin{verbatim}
*Jan14> fold_right (+) 0 [4,5,6]
15
*Jan14> 4 + (5 + (6 + 0))
15
*Jan14> fold_right (+) (-11) [4,5,6]
4
*Jan14> 4 + (5 + (6 + (-11)))
4
*Jan14> :t (++)
(++) :: [a] -> [a] -> [a]
*Jan14> :t fold_right (++) []
fold_right (++) [] :: [[a]] -> [a]
*Jan14> fold_right (++) [] [“hello”, [‘w’], “orld!”]
“helloworld!”
*Jan14> fold_right (++) [] [“hello”, [‘ ‘], [‘w’], “orld!”]
“hello world!”
*Jan14> :t “hello”
“hello” :: [Char]
*Jan14> foldr (++) [] [“hello”, [‘ ‘], [‘w’], “orld!”]
“hello world!”
*Jan14> foldr (++) [] [“hello”, [‘ ‘], “w”, “orld!”]
“hello world!”
\end{verbatim}
And now on to left:
\begin{code}
fold_left :: (b -> a -> b) -> b -> [a] -> b
fold_left f s [] = s
fold_left f s (x : xs) = fold_left f (f s x) xs
\end{code}
\begin{verbatim}
*Jan18> fold_left (+) 0 [4,5,6]
15
*Jan18> fold_left (++) [] [“hello”, [‘ ‘], “w”, “orld!”]
“hello world!”
*Jan18> fold_left (flip (++)) [] [“hello”, [‘ ‘], “w”, “orld!”]
“orld!w hello”
*Jan18> :t flip
flip :: (a -> b -> c) -> b -> a -> c
*Jan18> fold_left (flip (+)) 0 [4,5,6]
15
\end{verbatim}
Later on: “recursion schemes”
In functional languages, functions are first-class values.
Here is some very odd code:
\begin{code}
l :: [Integer]
l = 1 : 1 : zipWith (+) l (tail l)
\end{code}
\begin{code}
take’ :: Integer -> [a] -> [a]
take’ 0 _ = []
take’ 1 [] = []
take’ 1 (x:_) = [x]
take’ n [] = []
take’ n (x:xs) = x : take’ (n-1) xs
\end{code}
Polymorphism: two flavours:
\begin{itemize}
\item parametric polymorphism (in Haskell, free type variables in types
are implicitly universally quantified)
\item ad hoc polymorphism (i.e. overloading; in Haskell, via type classes)
\end{itemize}
Look at Eq first.
Class — ‘satisfy’ and ‘instance’ Haskell class is kind-of-sort-of-like a
Java Interface
instance resolution finds the “matching” instance and does dynamic dispatch
to the right one.
Then we did
\begin{verbatim}
:info Eq
:info Ord
:info Show
\end{verbatim}
(and I omit the voluminous output)