Functional Programming

Concepts of functional programming languages are increasingly introduced to imperative languages, for example, generics in C++, Java and C# or higher order functions in C++ and C#. But what is behind these concepts and what benefits do they offer in a declarative environment? To this end we study the purely functional programming language Haskell. Its programs are expressions whose values do not depend on the time of evaluation. There are no assignments, no states, no side effects and no modifiable variables. Higher order functions and lazy evaluation are instead used to modularise programs in new ways, making them more concise and comprehensible. Moreover, programs can be calculated with, for example, to prove their correctness and to derive optimised versions.

This lecture is an introduction to functional programming. We discuss basic concepts and topics such as algebraic data types, function definitions by patterns, list comprehensions, parametric type polymorphism, higher order functions, algorithm schemes, lazy evaluation, infinite data structures, type classes and monads. They are applied to problems from areas such as algorithms, program transformation and compiler construction. Haskell is used to communicate the skills, but they are profitably used to program in a functional style in other programming languages, too.

Bibliography

  • Richard Bird, Introduction to Functional Programming using Haskell, Prentice Hall, second edition, 1998.
  • Paul Hudak, The Haskell School of Expression: Learning Functional Programming through Multimedia, Cambridge University Press, 2000.
  • Graham Hutton, Programming in Haskell, Cambridge University Press, 2007.
  • Bryan O'Sullivan, Don Stewart, John Goerzen, Real World Haskell, O'Reilly, 2008.
  • Simon Thompson, Haskell: The Craft of Functional Programming, Addison Wesley, third edition, 2011.
  • Miran Lipovača, Learn You a Haskell for Great Good!, no starch press, 2011.