Introduction to Functional Programming
|Computer Laboratory > Course material 2002-03 > Introduction to Functional Programming|
Introduction to Functional Programming
Principal lecturer: Dr Gavin Bierman
It's all over!!!
|Yes, the course is over :-(|
|but you have a lifetime of happy SML coding ahead of you :-)|
|Please use the feedback to help us improve the course|
NOTE: You are now in a position to do all three sheets!
Material covered: Slides 1-12
This was a general introduction lecture to motivate the course. (Not helped by the projector not working. Funnily it started working at 11:03!)
I strongly recommend that you download an SML implementation and play. There are a number of good ones:
A paper detailing the prototyping experiment that I mentioned at the end of today's lecture can be found here (ps).
Material covered: Slides 13-25
Finally we got our hands on an SML implementation, and we did some elementary coding. We saw integers, reals, characters and strings. We also saw the wonder of n-ary tuples.
You can read about the SML basis library here
Material covered: Slides 26-33
Today we did some cool programming with lists. We saw the beautifully concise ML code to append and reverse lists. We also noticed that our length and reverse functions weren't that efficient, but we were able to code up efficient versions (and they're still beautiful!).
Material covered: Slides 34-41
Today we started off with a quick revision of what iterative functions were in ML. We then got on to looking at two sorting algorithms:
Material covered: Slides 42-51
Today we started with ML records. We then got on to the wonderful world of recursive datatype declarations. Isn't ML powerful? It's so easy to define complicated datatypes, and then pattern matching makes processing them really neat. depth and preorder etc. were particularly compact and readable.
Homework: Slide 50 contains code for three different ways of list tree elements. They're nice but use appends. Can you code them more efficiently?
Material covered: Slides 52-58
Today we did two funky things with trees, we simulated
We also looked at the sum datatype, which has two type variables! Some code is available here
Material covered: Slides 59-68
Today we entered the wonderful world of higher-order functions. ML allows you to pass in functions as arguments to other functions, and even allows functions to return a function as the result. Wow! We saw some neat matrix multiplication using these ideas. We also saw some "design patterns": the map, foldl and foldr functionals.
Oops! I forgot to clarify one important point. We saw that ML allowed us to write curried functions, e.g. instead of
fun sum (m,n) = m+n
of type int*int -> int we could write
fun sum m = fn n => m+n;
of type int -> (int -> int). ML provides a nice shorthand for the above code:
fun sum m n = m+n;
i.e. the space between the arguments means that the code is curried! This function is of type int -> (int -> int)
Material covered: Slides 69-77
Today we observed the lecturer's laptop decide that it was too old to be bothered to talk with projectors :-( We looked at how we can define lazy lists, i.e. lists where the next element is evaluated on demand. This allowed us to define sequences that were infinite!
Here is some code that generates an infinite tree of strings built up from characters A, B, and C, and selects those strings that are palindromes by both breadth-first and depth-first walking over the tree.
Material covered: Slides 78-86
Today we looked at proving some properties of ML code. Having proved that the code satisfies the property we don't need to bother with testing!
Material covered: Slides 87-95
Today we continued our study of proving properties of ML code. We looked at structural induction, and we proved some properties of code that worked on lists and on trees.
We also saw the coolest demos of FRAN - Conal Elliot's declarative approach to animation.
We went wow! at things like this:
which is generated from the following five lines of Haskell:
spiralTurn = turn3 zVector3 (pi*time) (unionGs (map ball [1 .. n])) where n = 40 ball i = withColorG color ( move3 motion ( stretch3 0.1 sphereLowRes )) where motion = vector3Spherical 1.5 (10*phi) phi phi = pi * fromInt i / fromInt n color = colorHSL (2*phi) 0.5 0.5
Material covered: Slides 96-109
Today we looked in more detail at SML's type system. In particular we looked quite carefully at how ML infers a type for an expression.
NOTE: The best way to understand this is to attempt some examples yourself. Try to work out the types of the following functions:
Material covered: Slides 110-end
Today we looked at a cute application area for SML: writing parsers. We discovered that the code for a parser looks almost exactly like the grammar: Cool!