School of Computer Science

Module 06-11582 (2010)

Software Workshop Haskell

Level 2/I

Antoni Diller Semester 1 10 credits
Co-ordinator: Antoni Diller
Reviewer: Robert Hendley

The Module Description is a strict subset of this Syllabus Page.

Aims

The aims of this module are to:

  • 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

Learning Outcomes

On successful completion of this module, the student should be able to:

  • 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

Teaching methods

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


Assessment

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

Detailed Syllabus

  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.

Programmes containing this module