Functional Programming

Synopsis

Programming with a functional notation: sessions and scripts, expressions and values. Evaluation of expressions. Case study: Approximating square roots. Reduction strategies: innermost vs outermost. [1]

Types and strong-typing. Basic types: Booleans and truth values. Simple programs involving pattern matching. Polymorphism and type classes. Functional application and currying. Functional composition. More types: characters, strings, tuples. Type synonyms. [2]

Lists and their operations; list comprehensions. The functions map, foldl, foldr, concat and filter. Many small examples illustrating the use of these functions in a compositional style of programming. [3]

Time complexity. Asymptotic notation. Advice on writing efficient programs; use of accumulating parameters. [2]

Recursion and induction. The algebraic properties of list functions and their proof by equational reasoning. Simple manipulation of programs to achieve efficiency. [2]

Infinite lists and their applications: Pascal's triangle, digits of a number, sieve of Eratosthesnes. Infinite lists as limits. Proving properties of infinite lists: induction, take lemma. Cyclic structures. [2]

Non-linear data structures. Binary trees and the relationship between size and depth. Binary search trees for representing sets. Insertion and searching in a binary search tree. Representing and evaluating arithmetic expressions. [3]

More advice on writing efficient programs: halve instead of decrease; tupling and accumulation. Space complexity and the use of strict. [1]

More substantial examples if time allows.