---
title: Functional Programming for Logicians - Lecture 4
subtitle: IO, Trees, Randomness
author: Malvin Gattinger
date: 17 January 2022
header-includes:
- \input{macros.tex}
---
> module L4 where
>
> import Data.Char
> import System.Random
\tableofcontents
IO
==
Summary Lecture 3
-----------------
Recall that:
- A `Functor` is something that we can `fmap` over.
- An `Applicative` is a `Functor` plus `pure` and `<*>`.
- A `Monad` is an `Applicative` plus `>>=`.
\bigskip
Examples: `Maybe`, `[ ]` and `IO` are monads!
Real World Haskell $^\ast$
-------------------------
Here are some useful standard IO functions:
λ> :t readFile
readFile :: FilePath -> IO String
λ> :t writeFile
writeFile :: FilePath -> String -> IO ()
λ> :t getLine
getLine :: IO String
λ> :t putStr
putStr :: String -> IO ()
λ> :t putStrLn
putStrLn :: String -> IO ()
\footnotesize
($^\ast$ This is also the title of the Haskell book by
Bryan O'Sullivan, Don Stewart, and John Goerzen.
See .)
Hello World 2.1
---------------
> dialogue :: IO ()
> dialogue = do
> putStrLn "Hello! Who are you?"
> name <- getLine
> putStrLn $ "Nice to meet you, " ++ name ++ "!"
> let capName = map toUpper name
> putStrLn $ "Or should I say " ++ capName ++ "?"
\vspace{1.5em}
. . .
Note that it is not\only<3>{$^\ast$} possible to "get out ouf `IO`" again.
Do not try to write functions like `f :: IO String -> String`.
\bigskip
\footnotesize
\pause
($^\ast$ It is, but `unsafePerformIO` is called like that for a reason.)
`sequence`
----------
We already called `<*>` the "sequence operator".
There is also a more general function: `sequence`.
It converts a list of actions into a single action that gives a list.
. . .
Example:
λ> sequence [Just 4, Just 12, Just 43]
Just [4,12,43]
. . .
Definition:
> mysequence :: Monad m => [m a] -> m [a]
> mysequence [] = return []
> mysequence (x:xs) = (:) <$> x <*> sequence xs
`sequence` with `IO`
--------------------
λ> :t replicate
replicate :: Int -> a -> [a]
λ> sequence (replicate 3 getLine)
bob
alice
carol
["bob","alice","carol"]
. . .
Similar to `foldl`, also `sequence` actually has a more general type:
\small
λ> :t sequence
sequence :: (Monad m, Traversable t) => t (m a) -> m (t a)
. . .
\bigskip
We will now look at another example of something `Traversable`.
Trees
=====
Example: trees
--------------
Binary-branching trees with things of type `a` at the leafs:
> data Tree a = Leaf a | Branch (Tree a) (Tree a)
> deriving (Eq,Ord,Show)
. . .
Example:
> numberTree :: Tree Int
> numberTree = Branch (Leaf 1) (Branch (Leaf 2) (Leaf 3))
`instance Functor Tree`
-----------------------
Let us define `fmap` for trees.
> instance Functor Tree where
> -- fmap :: (a -> b) -> Tree a -> Tree b
\vspace{-0.6em}
. . .
> fmap f (Leaf x) = Leaf (f x)
> fmap f (Branch left right) = Branch (fmap f left)
> (fmap f right)
. . .
Example:
λ> numberTree
Branch (Leaf 1) (Branch (Leaf 2) (Leaf 3))
λ> fmap (*10) numberTree
Branch (Leaf 10) (Branch (Leaf 20) (Leaf 30))
. . .
Note that `fmap` will never change the shape of the tree.
How does this compare to `fmap` for `Maybe`? \hmm
`instance Applicative Tree`
---------------------------
> instance Applicative Tree where
> -- pure :: a -> Tree a
> pure = Leaf
> -- (<*>) :: Tree (a -> b) -> Tree a -> Tree b
> (<*>) ftree (Leaf x) = fmap ($ x) ftree
> (<*>) ftree (Branch xl xr) = Branch (ftree <*> xl)
> (ftree <*> xr)
What does this do?
. . .
Example:
\footnotesize
λ> Branch (Leaf (+1)) (Leaf (+10)) <*> Branch (Leaf 3) (Leaf 4)
\vspace{-0.6em}
. . .
Branch (Branch (Leaf 4) (Leaf 13)) (Branch (Leaf 5) (Leaf 14))
Alternative `instance Applicative Tree`
---------------------------------------
We could also use the following `<*>` function,
recursing first on the tree of functions and then making full
copies of the value tree.
> star :: Tree (a -> b) -> Tree a -> Tree b
> star (Leaf f) atree = fmap f atree
> star (Branch fl fr) atree = Branch (fl `star` atree)
> (fr `star` atree)
. . .
Exercise: Check which way to implement `instance Applicative Tree`
fulfils the `Functor` and `Applicative` laws?
`instance Monad Tree`
---------------------
Wrapping up a thing into a tree is done using `Leaf`.
Binding a tree to `f` means we apply f to all its leafs.
\footnotesize
> instance Monad Tree where
> -- return :: a -> Tree a
> return = Leaf
> -- (>>=) :: Tree a -> (a -> Tree b) -> Tree b
> (>>=) (Leaf x) f = f x
> (>>=) (Branch left right) f = Branch (left >>= f) (right >>= f)
. . .
\normalsize
Example:
\scriptsize
λ> Branch (Leaf 5) (Leaf 8) >>= (\n -> Branch (Leaf (n+100)) (Leaf (n+10)))
Branch (Branch (Leaf 105) (Leaf 15)) (Branch (Leaf 108) (Leaf 18))
`Foldable` and `Traversable`
----------------------------
\tiny
type Traversable :: (* -> *) -> Constraint
class (Functor t, Foldable t) => Traversable t where
traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
sequenceA :: Applicative f => t (f a) -> f (t a)
mapM :: Monad m => (a -> m b) -> t a -> m (t b)
sequence :: Monad m => t (m a) -> m (t a)
{-# MINIMAL traverse | sequenceA #-}
. . .
type Foldable :: (* -> *) -> Constraint
class Foldable t where
Data.Foldable.fold :: Monoid m => t m -> m
foldMap :: Monoid m => (a -> m) -> t a -> m
Data.Foldable.foldMap' :: Monoid m => (a -> m) -> t a -> m
foldr :: (a -> b -> b) -> b -> t a -> b
Data.Foldable.foldr' :: (a -> b -> b) -> b -> t a -> b
foldl :: (b -> a -> b) -> b -> t a -> b
Data.Foldable.foldl' :: (b -> a -> b) -> b -> t a -> b
foldr1 :: (a -> a -> a) -> t a -> a
foldl1 :: (a -> a -> a) -> t a -> a
Data.Foldable.toList :: t a -> [a]
null :: t a -> Bool
length :: t a -> Int
elem :: Eq a => a -> t a -> Bool
maximum :: Ord a => t a -> a
minimum :: Ord a => t a -> a
sum :: Num a => t a -> a
product :: Num a => t a -> a
{-# MINIMAL foldMap | foldr #-}
`instance Foldable Tree`
-----------------------
\footnotesize
> instance Foldable Tree where
> -- foldr :: (a -> b -> b) -> b -> Tree a -> b
\vspace{-1.7em}
. . .
> foldr f y (Leaf x) = f x y
> foldr f y (Branch l r) = foldr f (foldr f y l) r
. . .
\bigskip
> instance Traversable Tree where
> -- traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
\vspace{-1.7em}
. . .
> traverse g (Leaf x) = Leaf <$> g x
> traverse g (Branch l r) = Branch <$> traverse g l <*> traverse g r
What is it good for?
--------------------
Now `foldr` and many more functions work on our trees:
λ> numberTree
Branch (Leaf 1) (Branch (Leaf 2) (Leaf 3))
λ> length numberTree
3
λ> sum numberTree
6
. . .
And we can execute a tree of IO actions!
λ> sequence $ Branch (Leaf (putStrLn "kwik"))
(Branch (Leaf (putStrLn "kwek"))
(Leaf (putStrLn "kwak")))
kwik
kwek
kwak
Branch (Leaf ()) (Branch (Leaf ()) (Leaf ()))
Other Trees
-----------
Exercise 3.4: Add things of type `a` at intermediate nodes.
. . .
Non-binary trees with arbitrary branching:
> data ArbTree a = Node a [ArbTree a]
Note that we no longer need an extra `Leaf` case.
Leafs are just `Node`s where the `[ArbTree a]` list of children is empty.
Exercise: Can you also make `ArbTree` a `Functor` etc.?
Randomness
==========
Random Integers
---------------
Getting a random value is obviously not a pure function.
To get a random integer we need interaction with the outside world.
(In UNIX this is usually `/dev/random` or `/dev/urandom`.)
> getRandomInt :: Int -> IO Int
> getRandomInt n = getStdRandom (randomR (0,n))
This gives:
λ> getRandomInt 20
16
λ> getRandomInt 20
18
Random Integer Lists
--------------------
\small
Generate an integer list with `n` entries in the range `[0..k]`.
> getInts :: Int -> Int -> IO [Int]
> getInts _ 0 = return []
> getInts k n =
> getRandomInt k >>= \x ->
> getInts k (n-1) >>= \xs -> do
> return (x:xs)
. . .
We can also write this "point-free":
> getInts'' :: Int -> Int -> IO [Int]
> getInts'' _ 0 = return []
> getInts'' k n = (:) <$> getRandomInt k <*> getInts'' k (n-1)
Random Lists of Random Integers
-------------------------------
Finally, we can also choose the parameters randomly:
> genIntList :: IO [Int]
> genIntList = do
> k <- getRandomInt 20
> n <- getRandomInt 10
> getInts k n
This gives, e.g.:
λ> genIntList
[0,0,0,0]
λ> genIntList
[-1,-5,-3,-2,-1,6,2,-8]
λ> genIntList
[15,-10,7,-15,5,-13,15,11,13,-11]
Project Practicalities
======================
Timeline
--------
- now: find a group (2 or 3 people) and topic
see
start reading material or explore existing code
- Friday 21st: send one email per group to Malvin:
Who are you, and what is your topic?
- next week: continue reading, shift to working
- Friday 28th: work-in-progress **presentations**
- Monday 31st: get feedback on current version (optional!)
- Friday 4th: **deadline for report**
Report Template
--------------
You should use this template for your project:
(For other larger Haskell projects, use `stack new` to create a new package with lots of boilerplate.)
Project Grading Criteria
------------------------
You will only get a pass/fail grade (and feedback comments).
Your final report:
- should have a specific topic and a concrete goal
- must be written in literate programming style
- should be well-structured
- must be at most 15 pages
Your program:
- must compile
- must have zero warnings with `-Wall`
- should generate zero hints from `hlint`
- should have tests
Your presentation:
- is about work-in-progress
- should be at most 20 minutes
- can be given by a subgroup
stack and cabal
---------------
Bigger projects
- use more than one `.hs` or `.lhs` file
- may depend on other Haskell libraries
To manage projects, we use `stack.yaml` and `package.yaml`.
. . .
\bigskip
The minimal `stack.yaml` is this:
resolver: lts-18.21
This refers to and hopefully ensures that your code still works next year.
\cross
Package management
------------------
The `package.yaml` describes your project and its **dependencies**:
\tiny
```
name: report
version: 0.1.0.0
synopsis: My Haskell report project
description: See report.pdf
maintainer: My Name
category: Logic
ghc-options: -Wall
dependencies:
- base >= 4.14 && < 5
- random
- QuickCheck
library:
source-dirs: lib
executables:
myprogram:
main: Main.lhs
source-dirs: exec
dependencies:
- report
tests:
simpletests:
main: simpletests.lhs
source-dirs: test
dependencies:
- report
- QuickCheck
- hspec
```
Version Control
---------------
Please use `git` when working in teams!
It takes half an hour, but you will then prevent the ``Dropbox problem'' of overwriting each others work.
For a tutorial,
[click here](https://guides.github.com/introduction/git-handbook/),
for a cheat sheet,
[click here](https://training.github.com/downloads/github-git-cheat-sheet/).
. . .
\bigskip
The most widely used hosted services for *git* are *github* and *gitlab*.
You may submit your report via email, but using git and a service like
`github` or `gitlab` is strongly preferred if you want to get help or
comments from Malvin during the next weeks.
---
\centering
\salad \hspace{1cm} \noodles
\bigskip
See you again at 13:00.
---
Bonus Content: History of the IO Monad
--------------------------------------
Since 1992 the most famous Monad is `IO`.
As told by Simon Peyton-Jones here, Haskell was useless at first:
(watch this from 31:20 until 38:22)
Bonus Content: Invention vs. Discovery
--------------------------------------
\centering
\includegraphics[height=10em]{img/wadler.jpg}
\begin{quote}
``Most of you use languages that were invented, and you can
tell, can’t you. This is my invitation to you to use
programming languages that are discovered.''
\flushright
Philip Wadler: \emph{Propositions as Types}
\end{quote}
\tiny
There are many recordings of this talk, but the original paper is this one: