Database Research Group

WSI – Database Systems Research Group

Functional Programming


News
  • Dec 15, 2015 — Aufgrund mangelnder Resonanz findet die Tutorensprechstunde ab sofort nicht mehr statt. — Alexander Ulrich


Numbers are values. Strings are values. Booleans are values. In "functional programming", functions 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.

Forum

Discussion around this course and Haskell in general are encouraged in the forum. Please stop by regularly, have a look, and say "hi".

Tutorial and Exercises

  • Regular weekly tutorials will only start on Monday, Nov 2.

  • Weekly exercise sheets are provided on the teaching platform ILIAS. Exercises are handed out (and submitted by you, a week later) Thursdays, at 10am.

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

  • Scoring well in the exercises leads to substantial bonus points in the final exam (up to ⅓ of the overall exam points).

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, OS X. Make sure to install the recent version 7.10.2.

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.


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.hshs
3lazy-factors.hshs
4infix-op.hs

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

hs
5factorial.hs

Demonstrates the use of guards in function definitions.

hs
6power.hs

Demonstrates the use of guards and local definitions (where).

hs
7bits.hs

Demonstrates the use of type synonyms (type ... = ...).

hs
8dictionary.hs

New example that demonstrates the use of

  • guards
  • type synonyms
  • head and tail to deconstruct a list.

NB: There are prettier and more concise ways to write function ageOf.

hs
9tally.hs

Demonstrates three equivalent variants (conditional, guards, pattern matching) of defining sum over lists.

hs
10take.hs

Demonstrates pattern matching over lists (reimplements function take).

hs
11ageOf.hs

Demonstrates pattern matching over lists of tuples (aka dictionaries).

hs
12mergesort.hs

Simple variant of the Mergesort algorithm (also demonstrates layered patterns v@p).

hs
13deriving.hs

Example that demonstrates sum types (enumerations) and the use of deriving to automatically define operations on these new types.

hs
14sequence.hs

Example that demonstrates a product types (maintains sequences ≡ a list of elements together with its length).

hs
15cons.hs

Defines a new list type List a that is isomorphic to Haskell's builtin list type [a]. Demonstrates sum-of-product types.

hs
16eval.hs

Defines a simple parse tree type Exp a for arithmetic expressions and a corresponding evaluation function. Demonstrates an algebraic tree type (≡ sum-of-product type).

hs
17rock-paper-scissor-inst.hs

Demonstrates the (somewhat tedious) explicit definition of class instances for user-defined algebraic data types via instance ... where.

hs
18rock-paper-scissor-inst-deriving.hs

Demonstrates the automatic derivation of class instances for user-defined algebraic data types (using deriving ...).

hs
19Mobile.hs

Solution to Assignment 4 (mobile rendering).

hs
20library-exposed.hs

Version ➀ of the IntegerSet DSL with fully exposed implementation details.

hs
21SetLanguage.hs (module)

Implementation of the IntegerSet DSL with representation details ([Integer]) hidden inside a module.

Module is imported by set-language-shallow.hs.

hs
22SetLanguageShallow.hs (module)

Re-implementation of the IntegerSet DSL with representation details (characteristic functions with type Integer -> Bool) hidden inside a module.

Module is imported by set-language-shallow.hs.

hs
23set-language-shallow.hs

Imports module SetLanguage (or SetLanguageShallow) to demonstrate that representation details remain hidden.

hs
24SetLanguageShallowCard.hs (module)

A shallow embedding of IntegerSet based on characteristic functions. This module includes a cardinality observer for sets.

hs
25set-language-deep.hs

Imports module SetLanguageDeepCard to demonstrate a deep embedding of the integer set DSL.

hs
26SetLanguageDeepCard.hs (module)

A deep embedding of IntegerSet based on characteristic functions. This module includes a cardinality observer for sets.

hs
27expr-deep-num.hs

Imports module ExprDeepNum to demonstrate a deep embedding of a simple expression language over integers.

hs
28ExprDeepNum.hs (module)

A deep embedding of a simple expression language over integers. Provides a Num instance to support a natural (domain-specific) infix operator syntax.

hs
29expr-language.hs

Imports module ExprDeep.hs to demonstrate the deep embedding of a simple uni-typed language over Integer and Bool literals. Note: expression e2 is not well-typed and will yield a runtime error when eval is applied.

hs
30ExprDeep.hs (module)

Deep embedding of a simple expression language over Integer and Bool literals. Uses standard algebraic datatypes to provide an untyped representation.

hs
31expr-language-typed.hs

Imports module ExprDeepGADTTyped.hs to demonstrate a typed deep embedding of a simple uni-typed language over Integer and Bool literals. Note: expression e2 is not well-typed and will yield a compile-time type error.

hs
32ExprDeepGADTTyped.hs (module)

A typed and deep embedding of a simple expression language over Integer and Bool literals. Uses generalized algebraic data types (GADTs) to tell expression over integers and Booleans apart at compile time.

hs
33expr-embeddings.hs

Exercises the three types of embeddings (two shallow, one deep) of an expression language with let ... in as provided by module ExprEmbeddings.hs. Contains a basic iterative expression simplifier to be used with the deep embedding.

hs
34ExprEmbeddings.hs (module)

Two shallow and one deep embedding for a simple arithmetic expression DSL that features a let ... in construct.

hs
35pattern-match.hs

Initial simple pattern matching examples. Uses module PatternMatching.hs.

hs
36pattern-matching.hs

More examples for string pattern matching. Uses composite patterns to match simple arithmetic expressions. Returns either the matched characters or an abstract syntax tree for the matched expressions. Uses module PatternMatching.hs.

hs
37PatternMatching.hs (module)

A module that implements a simple DSL for string pattern matching. Implementation based on the replace failure by a list of successes technique.

hs
38normal-order.hs

Demonstrates that normal order reduction (pick outermost redex first) avoids the evaluation of the bomb.

hs
39bottom.hs

Demonstrates that non-strict functions can be evaluated successfully even if (some of) their arguments are ⊥ (bottom).

NB: Haskell functions are strict in all arguments that undergo pattern matching.

hs
40sharing.hs

Attemtps to provide an intuition of how sharing avoids the duplication of work.

Note: function trace (module Debug.Trace) writes its first argument to the console and then returns its second argument.

hs
41min=head-isort.hs

A folklore example of how lazy evaluation to WHNF may lead to non-intuitive complexity: a declarative definition of list minimum min that sorts its list argument and returns the head. Complexity still is O(n).

hs
42newton-raphson.hs

An implementation of the Newton-Raphson approximation of the square root √x. Based on a generator/test function pair which are specified indepdendently. Relies on lazy evaluation to consume the potentially infinite list produced by the generator iterate.

hs
43tic-tac-toe.hs

Construction and (static as well as forward-looking) evaluation of a game tree for the board game Tic Tac Toe. Relies on lazy evaluation to only generate the relevant parts of the otherwise large game tree (α-β algorithm).

hs
44round.hs

Demonstrates one use of the Functor instance for the type constructor Either String.

hs
45break-the-law.hs

Demonstrates how the laws of Functor are violated if the implementation of fmap fiddles with the container/context. Example: swap the T and F constructors to get

fmap  T           = F
fmap  F           = T

to see how the law is violated.

hs
46Validation.hs (module)

A Haskell module that implements data type Validation e a which represents a value of type a whose computation has generated the (error/validation) messages e. Typically, e will be a list type (or some other instance of Monoid that allows the combination of individual messages).

hs
47validate.hs

Uses module Validation.hs to showcase the Validation data type (validates minimum/maximum length of a username and password). A series of such validations is combined via <*> in the so-called applicative style.

hs
48sequence-Maybe.hs

Demonstrates the sequencing of functions of type a -> Maybe b. Defines operator (>=>) to hide the necessary plumbing.

hs
49sequence-Either.hs

Demonstrates the sequencing of functions of type a -> Exc b (where Exc b models a computation that can succeed with value of type b or yield an exception). Defines operator (>=>) to hide the necessary plumbing.

hs
50sequence-NonDet.hs

Demonstrates the sequencing of non-deterministic functions of type a -> NonDet b (where NonDet b is [b] to model a choice of possible answers). Defines operator (>=>) to hide the necessary plumbing.

hs
51sequence-ST.hs

Demonstrates the sequencing of functions of type a -> ST b (where the state transformer type ST b = State -> (State, b) models functions that receive the current state and may generate a new state along with their regular result of type b). Defines operator (>=>) to hide the necessary plumbing.

hs
52monadic-Maybe.hs

Uses monadic style (>>= and return) to sequence functions of type a -> Maybe b. Uses the Haskell-provided Monad instance for Maybe.

hs
53monadic-Either.hs

Uses monadic style (>>= and return) to sequence functions of type a -> Exc b (which is isomorphic to Either). Provides its own instances for Monad (and Applicative, Functor).

hs
54monadic-NonDet.hs

Uses monadic style (>>= and return) to sequence functions of type a -> NonDet b (which is isomorphic to [b]). Provides its own instances for Monad (and Applicative, Functor).

Uses non-deterministic functions to model the solution of a puzzle.

hs
55monadic-do-NonDet.hs

Uses monadic style in do-notation to sequence functions of type a -> NonDet b (which is isomorphic to [b]). Provides its own instances for Monad (and Applicative, Functor).

Uses non-deterministic functions to model the solution of a puzzle.

hs
56monadic-ST.hs

Uses monadic style (>>= and return) to demonstrate the sequencing of functions of type a -> ST b (where the state transformer type ST b = State -> (State, b) models functions that receive the current state and may generate a new state along with their regular result of type b).

hs