Announcements
Project proposals due by end of this week
“Pascal [Java] is for building pyramids …. Lisp [Haskell] is for building organisms – …. The organizing principles used are the same in both cases, except for one extraordinarily important difference: The discretionary exportable functionality entrusted to the individual Lisp programmer is more than an order of magnitude greater than that to be found within Pascal enterprises. Lisp programs inflate libraries with functions whose utility transcends the application that produced them. In Pascal the plethora of declarable data structures induces a specialization within functions that inhibits and penalizes casual cooperation.
– Alan J. Perlis, Foreword to “Structure and Interpretation of Computer Programs”, 1985, 1996
CPSC 312 — Lecture 12 1 / 8
©D. Poole 2021
Review
type defines a type name as an abbreviation for other types data defines new 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
CPSC 312 — Lecture 12 2 / 8
©D. Poole 2021
How to write a (Haskell) Program
To solve a complex problem, break it into simpler problems. Motivate/design top-down
Build bottom-up.
Write a clear specification (API / intended interpretation) for each component; program to that specification.
Ensure each part is modular, debuggable, with clear meaning. Test early and test often. Try to break your program.
Try to prove your program is correct.
Test every function when defined. Every component of a function should be already tested and debugged before use. Give the type signature for every function (so the compiler does not suggest bugs in tested code).
Generalize components so they are as reusable as possible. Make sure you can find a previously written appropriate function when it is the one you want.
Write functional components as much as possible.
Try to minimize IO components.
©D. Poole 2021 CPSC 312 — Lecture 12 3 / 8 (So it is easier to debug, check correctness,..)
Handling Unknown Types
When reading a CSV file, we get strings. Sometimes we want to use the numbers in CSV file, but we don’t know the type when writing the program.
How can we do this with Haskell’s strong typing?
Solution: have a type that can have heterogeneous types using constructors.
See Features.hs
CPSC 312 — Lecture 12 4 / 8
©D. Poole 2021
Games (MagicSum.hs, Play.hs)
Players make actions
Games take actions and update state of game, perhaps
finishing.
A player, given state of game, and a list of legal actions, selects an action
A game: function from action and state into a result. A result is either:
End of game with result = value for player, (e.g., +1 for win, 0 for draw/tie, -1 for loss) and a new starting state, or
Game continues with a new state
CPSC 312 — Lecture 12 5 / 8
©D. Poole 2021
Game Abstraction (See MagicSum.hs Play.hs)
type Player = State -> Action
A player is given a state of the game and selects a move.
type Game = Action -> State -> Result
A game takes an action and the state and returns a result Result is either
the end of the game with a reward and starting state or a continue with a new state
data Result = EndOfGame Double State
| ContinueGame State
As part of the state is internal state and the available moves:
data State = State InternalState [Action]
State is threaded through the code (a state is input and a state is output).
Callers should not make any assumptions about the form of the internal state or the actions.
CPSC 312 — Lecture 12 6 / 8
©D. Poole 2021
Magic Sum Game
players take turns choosing different numbers in range [0..9] first player to have 3 numbers that sum to 15 wins
draw/tie if run out of numbers to play
What common game is this equivalent to?
276 Magic square: 9 5 1 438
Magic sum game is isomorphic to tic-tac-toe.
CPSC 312 — Lecture 12
7 / 8
©D. Poole 2021
Magic Sum Game
players take turns choosing different numbers in range [0..9] first player to have 3 numbers that sum to 15 wins
draw/tie if run out of numbers to play
What information does a state contain?
(Numbers chosen by self, numbers chosen by opponent)
What Actions are available?
List of numbers not chosen.
CPSC 312 — Lecture 12 8 / 8
©D. Poole 2021