Database Research Group

WSI – Database Systems Research Group

Functional Programming



Numbers are values. Strings are values. Booleans are values. In Functional Programming, functions simply are simply values as well. This view on programming leads to an elegant and expressive programming paradigm which we will investigate in this course. During the course, we will use the programming language Haskell. The majority of the concepts we will consider applies in other (functional) languages as well.

Participants are not expected to be fluent in Haskell from the beginning. We will spend the first three weeks of the semester on a Haskell Ramp-Up. Things will progress rather fast, though. The majority of the semester will be used for the good stuff: intermediate and advanced topics, of which there are plenty.

Syllabus

This course will provide an introduction to Haskell (first half) and then touch on intermediate-level topics. We will discuss (topics in parentheses will be addressed if we'll find the time):

  • Values and types
  • Function definitions (guards, pattern matching)
  • List processing
  • Algebraic data types
  • Type classes
  • Domain-specific languages (DSLs; shallow and deep embedding)
  • Laziness
  • Functors. Applicative Functors, Monads
  • (Monadic parsing)
  • (Applications: breadth-first search, path finding)

Forum

Discussion around this course and Haskell in general are encouraged in the forum. ⚠️ If you want to participate in the exercises, you absolutely need to register in the forum, as we use it to create/administer student accounts in this course. Thus, please stop by regularly, have a look, and say "hi".

Tutorial and Exercises

  • We will provide weekly exercise sheets (hand-out: Friday, hand-in by Thursday night).

  • You are admitted to the final exam if you score at least ⅔ of the overall exercise points.

  • Scoring well in the exercises leads to bonus points in the final exam.

Haskell (GHC, Haskell Platform)

The course will use the de-facto standard Haskell compiler GHC and its interactive variant (also known as read-eval-print loop or REPL) GHCi. We strongly suggest you download and install the so-called Haskell Platform which includes both GHC and GHCi (and more). Available for virtually all operating systems, including Windows, Linux, macOS. Make sure to install the recent version.

Literature

The following introductory books and courses on Haskell are recommend reading — some of these are available online:

We will refer to additional material for the individual topics during the semester.


Slides
NrChapterDownload
1

Welcome + Haskell Ramp-Up

Reduction, values, types, expressions, function definitions

pdf
2

Haskell Ramp-Up (Part 2)

Algebraic data types, type classes

pdf
3

Domain-Specific Languages (DSLs)

Modules, abstract data types, shallow + deep embedding of DSLs

pdf
Additional material (code, data)
NrFileDownload
1chewie.hs

The Hello, World! of Haskell.

  1. Compile with Haskell compiler ghc via ghc --make chewie.hs, execute on the command line with ./chewie.
  2. Load into REPL ghci via ghci chewie.hs, then evaluate function main.
hs
2isPrime.hs

Prime number test. Efficient thanks to lazy evaluation of factors (a comparison with the empty list [] can be decided once the first element of factors has been found).

hs
3infix-op.hs

Demonstrates the definition of user-defined operator ~=~.

hs
4factorial.hs

Compute the factorial n! of natural number n. Defines two equivalent variants of the function that demonstrate the use of conditional expressions (if...then...else...) and guards.

hs
5power.hs

Two equivalent formulations of an efficient power computation. Demonstrates the use of guards, local definitions (where, let … in) and explicit layout syntax using {,} and;.

hs
6bits.hs

A demonstration of type synonyms (type t₁ = t₂) and list processing (determine the bit list of an Integer value).

hs
7sum.hs

A reimplementation of the sum built-in function: sum all elements of a list. Two formulations: guards and pattern matching.

hs
8take.hs

A reimplementation of the built-in take function: extract a prefix (of given length) from a list.

hs
9mergesort.hs

An implementation of MergeSort in Haskell. Builds on the merge function developed in the lecture.

hs
10deriving.hs

Definition of and functions over sum data types (Weekday, Move, Outcome). Uses deriving to define basic operations like equality, ordering, showing, ...

hs
11sequence.hs

Definition and functions over product type Sequence.

hs
12cons.hs

Defines algebraic data type List a and shows that it is isomorphic to the builtin type constructor [a]. Uses lifting to lift regular list-processing functions from [a] to List a.

hs
13eval-compile-run.hs

Defines abstract syntax trees for simple arithmetic expressions Exp a and implements an interpreter (≡ evaluation function eval), compiler (compile) and mini stack-based virtual machine (run).

Interpreter as well as compiler and VM are related:

∀ e :: Num a => Exp a: (run [] . compile) e == eval e

hs
14searchFor.hs

Function searchFor performs a lookup in a key/value-dictionary, provided that the key type supports equality comparisons.

(An equivalent function is already built into Haskell's Prelude: lookup.)

hs