Database Research Group

WSI – Database Systems Research Group

Functional Programming



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.

Exercises

Weekly exercise sheets are provided on the teaching platform Ilias. Please register at the following link for the exercises: Functional Programming in Ilias. The first exercise sheet will be handed out on Monday, 14.04.2014 at 14:00.

Literature

The following introductory books on Haskell are available online:

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


Additional material (code, data)
NrFileDownload
1ice-cream.hs

The Hello, World! of Haskell.

  1. Compile with Haskell compiler ghc via ghc --make ice-cream.hs, execute with ./ice-cream.
  2. Load into REPL ghci via ghci ice-cream.hs, then evaluate function main.
hs
2isPrime.hshs
3lazy-factors.hshs
4infix-op.hs

Declares a user-defined infix operator ~=~ (approximately equality)

hs
5factorial.hs

Conditional expression vs. guards

hs
6power.hs

Function definition using guards and local where bindings

hs
7tally.hs

Conditional expression vs. guards vs. pattern matching

hs
8take.hs

Compute a finite prefix of an (infinite) list — demonstrates pattern matching

hs
9mergesort.hs

Mergesort (with a user-defined ordering relation) — demonstrates pattern matching, local where bindings, guards

hs
10weekday.hs

Demonstrates algebraic sum types (enumerations)

hs
11sequence.hs

Demonstrates algebraic product types

hs
12cons.hs

Demonstrates algebraic sum-of-product types (cons lists)

hs
13eval-compile-run.hs

Use algebraic data types to represent, evaluate, compile, and execute simple arithmetic expressions

hs
14rock-paper-scissor-inst.hs

Manually implement Eq, Ord, Enum, Bounded, and Show type class instances for user-defined data types

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

Use deriving to generate selected type class instances automatically

hs
16library-exposed.hs

Implements integer sets as unordered lists, implementation fully exposed

hs
17SetLanguageShallowCard.hs

Shallow embedding of a DSL for integer sets (uses a Haskell module to hide the implementation in terms of characteristic functions)

hs
18set-language-shallow.hs

Imports and exercises the shallow integer set DSL embedding in SetLanguageShallowCard.hs

hs
19SetLanguageDeepCard.hs

Deep embedding of a DSL for integer sets (observers member and card)

hs
20set-language-deep.hs

Imports and exercises the deeply embedded integer set DSL in module SetLanguageDeepCard

hs
21ExprDeepNum.hs

Deep embedding of a super-simple expression language (with eval observer). Instance of Num to provide natural syntax for the DSL.

hs
22expr-deep-num.hs

Imports ExprDeepNum

hs
23ExprDeepGADTTyped.hs

Using GADTs to construct a type-safe deeply embedded DSL over integers and Booleans.

hs
24expr-language-typed.hs

Imports ExprGADTTyped

hs
25ExprShallowPrint.hs

Shallow embedding of a DSL for expressions with let-bindings. Class-based, observers for evaluation and printing implemented as instances.

hs
26expr-language-shallow-print.hs

Imports ExprShallowPrint

hs
27PatternMatching.hs

A shallowly embedded DSL for string pattern matching. Based on Philip Wadler's seminal 1985 paper Replacing Failure by a List of Successes.

hs
28simple-patterns.hs

Imports PatternMatching

hs
29pattern-matching.hs

Imports PatternMatching to parse fully-parenthesized expressions

hs
30sequence-Maybe.hs

Sequencing partial functions a -> Maybe b using Kleisli composition (>=>)

hs
31sequence-Either.hs

Sequencing exception-generating functions a -> Exc b using Kleisli composition (>=>)

hs
32sequence-ST.hs

Sequencing stateful functions a -> ST b using Kleisli composition (>=>)

hs
33monadic-Maybe.hs

Monadic sequencing of partial functions a -> Maybe b using return and bind (>>=)

hs
34monadic-Either.hs

Monadic sequencing of exception-generating functions a -> Exc b using return and bind (>>=)

hs
35monadic-NonDet.hs

Monadic sequencing of non-deterministic functions (i.e., relations) a -> NonDet b using return and bind (>>=)

hs
36monadic-ST.hs

Monadic sequencing of stateful functions a -> ST b using return and bind (>>=)

hs
37monadic-do-NonDet.hs

Reformulating monadic-NonDet.hs using Haskell's do-notation

hs
38IOaction.hs

Demonstrates how the construction of IO actions is decoupled from their effectful execution (free monad IOaction)

hs
39Perhaps.hs

Data type Perhaps of values/probabilities and its associated monad

hs
40hiking.hs

Super-simple demonstration of the Perhaps monad

hs
41Probability.hs

Monad Dist of probability distributions (built by layering the list and Perhaps monads) along with few supporting combinators

hs
42dice.hs

Throwing one die/two dice and the resulting probability distribution (uses Probability.hs)

hs
43parFibPie.hs

Using primitives par and pseq to parallelize the evaluation of two independent computational tasks.

Compile via ghc -O2 -threaded -rtsopts -eventlog --make parFibPie.hs, execute via ./parFibPie +RTS -N2 -s -l.

Spark profile can be inspected via ThreadScope.

hs
44parFibPies-force.hs

Using force (module Control.DeepSeq) to request normal form reduction (of lists) when parallelizing via par and pseq.

hs
45DeepSeq.hs

Making a user-defined algebraic data type an instance of class NFData (types whose values can be explicitly reduced to normal form).

hs
46ParIndices.hs

A parallel variant of elemIndices (find the indices of all occurrences of an element in a sequence). Uses chunking to create even-sized sub-problems to be evaluated in separate threads.

hs
47indices.hs

Wrapper that measures execution time of parIndices (see ParIndices.hs).

Execute via ./indices +RTS -A2G -K2G -N<n> -s -l where <n> denotes the number of (hyper-threaded) CPUs to use for parallel evaluation.

hs
48ParFoldMap.hs

Parallel monoid reduction (parFoldMap) of a sequence using an arbitrary monoid m.

hs
49Wookie.txt

Illustration: Splitting an input text into its whitespace-separated words. A formulation of the problem in terms of Chunks and Segments (from which a monoid is easily derived, see WordState.hs)

txt
50WordState.hs

A Monoid instance for the Chunk and Segment representation of an input text. Used in allWords.hs to split an input file into its whitespace-separated words.

hs
51allWords.hs

Uses parallel monoid reduction (over monoid WordState) to split the contents of a text file into its whitespace-separated words. Uses ParFoldMap.hs and WordState.hs.

⚠ Replace "war-and-peace-10x.txt" with the name of a suitabll large text file (20+ MB) on your local disk.

Execute via ./allWords +RTS -K2G -A2G -N<n> -s -l.

hs