Module 06-11582 (2011)

• present the basic ideas of the pure functional programming language Haskell
• demonstrate the main elements of good programming style
• illustrate some of the uses and applications of Haskell

• demonstrate an understanding of the main features and advantages of a functional language.
• write programs and implement algorithms in a functional style
• use functional programming techniques to solve problems
• use higher-order and list-manipulating functions
• use various data types appropriately in the solution of problems
• demonstrate an understanding in general terms of how a functional language is implemented

Ten one-hour weekly lectures plus ten three-hour demonstrator-supervised laboratory sessions.

• Sessional: 1.5 hr examination (80%), coursework (20%).
• Supplementary: By examination only (100%).

1. Introduction: aims of the module; structure and organisation of the module; assessment; teaching methods; style of presentation; useful books.
2. Functional language paradigm: uses; implementation; history; main features; advantages and disadvantages; languages (Lisp, Hope, ML, SASL, KRC, Miranda (tm), Orwell, Haskell); why Haskell is the best.
3. Haskell: various implementations (Gofer, HUGS98 and others); the HUGS98 system; system commands; sessions and scripts; fundamental ideas (higher-order functions, currying, uncurrying, sections, function composition, recursion, local definitions, Landin's off-side rule); programming style; literate scripts; the standard prelude; type systems; qualified types.
4. Numbers: basic operations (addition, subtraction, multiplication and so on); basic numerical types (Int, Integer, Float, Double); numerical type classes (Num, Integral, Real, Fractional).
5. Lists: basic operations (concatenation, concat, reverse, length, head, tail, init, last, take, drop, indexing, map, filter, zip, unzip and so on); list comprehensions.
6. Homomorphisms: various operators (foldr, foldl, foldr1, foldl1, scanr, scanl, scanr1, scanl1); duality theorems; fusion.
7. Programming techniques: executable specifications; program transformation; source reduction; partial evaluation; accumulating parameters; tupling; memoisation or tabulation; divide-and-conquer functions; continuations.
8. Advanced features: modules; monads; interactive programs; lazy evaluation; proving properties possessed by programs; harmful effects of deductivist style and Euclidean methodology.
9. Animation: executable and formal specification; representing types; implementing operations; choosing the state space.
10. Types: basic types (Int, Integer, Float, Double, Bool, Char); type classes (Text, Eq, Ord, Num, Integral, Real, Fractional); enumerations; recursive datatypes (trees and others).
11. Combinatory logic: contraction; reduction; normal forms; various systems; Church-Rosser Theorem and other useful properties; bracket abstraction algorithms; bases; fixed-point combinators; Curry-Howard isomorphism.
12. Type theory: design issues; systems (non-existent, monomorphic, polymorphic, other); motivation; type-free lambda-calculi; Curry-style typed lambda-calculi; Church-style typed lambda-calculi; type-inference and type-assignment; Curry-Howard isomorphism.