Announcements
Midterm #2 next Monday ¡ª see the course web site for more details (same format as Midterm 1, including you can write up to 24 hours early)
Watch Pizza for booking project demos
One must learn by doing the thing; for though you think you know it, you have no certainty until you try.
Sophocles (¡Ö 497- 406 BCE)
CPSC 312 ¡ª Lecture 17 1 / 15
ýD. Poole 2021
Review: Haskell since midterm
type defines a type name as an abbreviation for other types data defines new data structures (and a type) and
constructors / deconstuctors
IO t is the input/output monad
do can be used to sequence input/output operations
newtype is like data but with more restrictions (and no runtime overhead)
Type constructors and type variables
CPSC 312 ¡ª Lecture 17 2 / 15
ýD. Poole 2021
Last week
Abstraction for games, so we can write interfaces and solvers for any games that fit the abstraction
Representation of magic-sum game and count game A simple human interface for the abstraction
mm_player: a player that searches through all possible games and returns a best move. (Using minimax).
Make minimax more efficient (Caching / Memoization) Abstract data types
Threading state and memoization
Trees and functions as implementations for dictionaries
Today:
Defining classes and higer level abstractions
CPSC 312 ¡ª Lecture 17 3 / 15
ýD. Poole 2021
Clicker Questions
For the two definitions of Hash for lists:
i) instance Hash t => Hash [t] where hash [] = 17413
hash (h:t) = hash ( hash h + hash t)
ii) instance Hash t => Hash [t] where
hash lst = hash (sum [hash e | e <- lst]+17413)
Which one always maps permutations (different orderings of same values) to the same value?
A Both (i) and (ii) B (i) but not (ii) C (ii) but not (i) D neither
ýD. Poole 2021
CPSC 312 ¡ª Lecture 17 4 / 15
Building a game abstraction
What do we need to represent:
Magic sum game and other ¡°fully observable¡± games Blackjack (or other card game)
Adventure game where agent can move around, collect rewards, get penalties (without necessarily turn-taking with an opponent)
Agents that can have state (e.g., agents that learn)
Multiple games at the same time (e.g, simultaneously play magic sum and count games)
Questions
What did we need to put the game abstraction at the top of the Magic sum game?
What is wrong with having
type Player = State -> Action See: Games2.hs
CPSC 312 ¡ª Lecture 17 5 / 15
ýD. Poole 2021
An interface for games (Games2.hs)
— gs=game_state act=action
data State gs act = State gs [act]
deriving (Ord, Eq, Show)
data Result gs act =
EndOfGame String Double (State gs act)
| ContinueGame Double (State gs act)
deriving (Eq, Show)
type Game gs act = act -> State gs act -> Result gs act
— gs=game_state act=action ps=player_state
type Player gs act ps = Game gs act -> State gs act
-> ps -> (act, ps)
ýD. Poole 2021
CPSC 312 ¡ª Lecture 17 6 / 15
Clicker Question
data State gs act = State gs [act]
data Result gs act =
EndOfGame String Double (State gs act)
| ContinueGame Double (State gs act)
What is not true?
A State is both a type constructor and a function B The State function takes a gs and a list of act C EndOfGame is a function that takes 3 arguments D Result is a function that takes 2 arguments
ýD. Poole 2021
CPSC 312 ¡ª Lecture 17 7 / 15
Clicker Question
data State gs act = State gs [act]
data Result gs act =
EndOfGame String Double (State gs act)
| ContinueGame Double (State gs act)
———————————-**************
The (State gs act) above the stars
A Gives an error because act should be in square brackets B Refers to the type construtor for State
C Refers to the function State
D Doesn¡¯t need the gs act arguments
ýD. Poole 2021
CPSC 312 ¡ª Lecture 17 8 / 15
Clicker Question
data Result gs act =
EndOfGame String Double (State gs act)
| ContinueGame Double (State gs act)
deriving (Eq, Show)
What is not true:
A gs is a type variable
B EndOfGame “Fun” 7 iv
is of type Result as long as iv is of type act.
C At compile time gs needs to be resolved into an actual type D ContinueGame is a function that takes 2 arguments
ýD. Poole 2021
CPSC 312 ¡ª Lecture 17 9 / 15
Clicker Question
If we were to have:
type Game mt st init
= Action mt st init -> Result mt st init
What is true:
A Everything of type Game is a function that takes one argument
C Everything of type Game is a function that takes three arguments
D We cannot tell what something of type Game is from this declaration
ýD. Poole 2021
CPSC 312 ¡ª Lecture 17 10 / 15
Clicker Question
Consider the following form:
map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs
What is the value of map (+1) [2,3,4] A [3,4,5]
B 10
C [5,4,3]
D It gives a runtime error E It gives an type error
ýD. Poole 2021
CPSC 312 ¡ª Lecture 17 11 / 15
Clicker Question
Consider the following form:
data Maybe a = Just a
| Nothing
mmap :: (a -> b) -> Maybe a -> Maybe b
mmap f Nothing = Nothing
mmap f (Just x) = Just (f x)
What is the value of
(mmap (+1) (Just 5), mmap (+1) Nothing) A (Nothing, Nothing)
B Nothing
C (Just 6, Nothing)
D It gives a runtime error E It gives an type error
ýD. Poole 2021
CPSC 312 ¡ª Lecture 17 12 / 15
Maps and Functors
map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs
mmap :: (a -> b) -> Maybe a -> Maybe b
mmap f Nothing = Nothing
mmap f (Just x) = Just (f x)
class Functor p where
fmap :: (a -> b) -> p a -> p b
instance Functor Maybe where
— fmap :: (a -> b) -> Maybe a -> Maybe b
fmap f Nothing = Nothing
fmap f (Just x) = Just (f x)
ýD. Poole 2021
CPSC 312 ¡ª Lecture 17 13 / 15
Making a Binary search tree into a functor (BSTree2.hs)
— a binary search tree
— k is the key type; v is the value type
data BSTree k v = Empty
| Node k v (BSTree k v) (BSTree k v)
class Functor p where
fmap :: (a -> b) -> p a -> p b
How should a functor work for a binary search tree?
instance Functor (BStree k) where
— fmap :: (a -> b) -> BStree k a -> BSTree k b
fmap f Empty = Empty
fmap f (Node key val t1 t2)
= Node key (f val) (fmap f t1) (fmap f t2)
ýD. Poole 2021
CPSC 312 ¡ª Lecture 17 14 / 15
Redefining show for card games (Games2.hs)
What if we also want to include blackjack?
Actions: Flip, Hold
State: current count and the deck
The state for blackjack includes the deck, but the player shouldn¡¯t see or have access to the deck!!
Don¡¯t export the constructor:
data Rands = RandsC [Double]
instance Show Rands where
show d = “_”
instance Eq Rands where
x == y = True
instance Ord Rands where
— x < y = False
x <= y = True
-- random numbers
Deck is an infinite list of numbers.
Generating random numbers with a seed from system can only be done in IO.
But the infinte list can be passed as an argument.
ýD. Poole 2021 CPSC 312 ¡ª Lecture 17 15 / 15