Database Research Group

WSI – Database Systems Research Group

Functional Programming


News
  • Sep 11, 2017 — Hallo zusammen,

    die Wiederholungsprüfungen zur Veranstaltung "Functional Programming" (SS17) werden am Vormittag des Montag, den 9.10.2017 statt finden.

    Die Prüfungen werden mündlich abgenommen. Bitte meldet euch bei mir bis spätestens 29. 09. 2017 zur Prüfung an (b.dietrich@uni-tuebingen.de). Die Vergabe konkreter Termine erfolgt im Anschluss. Eine separate Anmeldung im Campus-System ist nicht erforderlich.

    Zur Teilnahme zugelassen sind grundsätzlich all diejenigen, die die Hauptklausur nicht bestanden haben oder dieser entschuldigt fern geblieben sind.

    Viele Grüße Benjamin — Benjamin Dietrich

  • May 16, 2017 — Die Übung zur VL Functional Programming heute Nachmittag muss wegen Krankheit leider ausfallen. Die nächste Übung ist dann am kommenden Dienstag. — Benjamin Dietrich

  • Apr 20, 2017 — Die Anmeldung zu den Übungen in "Funktional Programming” ist nun freigeschaltet. Wir weden zur Übungsorganisation GitHub Classroom, sowie unser Forum einsetzen.

    Bitte folgt dieser Anleitung, um euch zu den Übungen anzumelden.

    Es werden in der Regel wöchentlich, jeweils Freitags Übungsblätter ausgegeben. Lösungen müssen immer bis einschließlich Donnerstag der Folgewoche (23:59 Uhr) abgegeben werden. Ein erstes Übungsblatt wird morgen, am Fr. 21.04.17, erscheinen.

    Eine Besprechung der Übungsblätter findet im Tutorium, Dienstags von 14-16 Uhr, statt. Der erste Termin ist am Di. 25.04.17. Inhaltlich werden wir dann noch nicht sonderlich weit fortgeschritten sein, es können dort aber Fragen zur Installation und Nutzung der Tools, sowie zur Organisation geklärt werden. Die Teilnahme am Tutorium ist nicht verpflichtend.

    Ich freue mich auf das kommende Semester mit euch!

    Beste Grüße Benjamin — Benjamin Dietrich


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.

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. Please stop by regularly, have a look, and say "hi".

Tutorial and Exercises

  • Regular weekly tutorials will only start on Tuesday, April 25.

  • We will provide weekly exercise sheets.

  • 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.

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 8.0.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.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

Two equivalent formulations of the factorial (n!) function (using if ... then ... else and guards).

hs
5power.hs

Two equivalent formulations of an efficient power computation. Demonstrates the use of guards and local definitions (where, let … in).

(demonstrated at the tutorial on Tue, 2nd May 2017)

hs
6bits.hs

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

hs
7tally.hs

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

hs
8ageOf.hs

Search in an association list. Failure is handled using the Maybe a data type constructor.

hs
9take.hs

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

hs
10deriving.hs

Definition of and functions over sum data types (Weekday, Sequence). 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.hs

Defines abstract syntax trees for simple arithmetic expressions Exp a and implements an interpreter (≡ evaluation function eval).

hs
14eval-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
15class.hs

A simple demonstration of a type class C and how its method foo can be "overloaded" by several class instances.

hs
16library-exposed.hs

First version of the IntegerSet DSL with fully exposed implementation details.

hs
17SetLanguageShallow.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
18set-language-shallow.hs

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

hs
19SetLanguageShallowCard.hs (module)

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

hs
20SetLanguageDeep.hs (module)

A deep embedding of IntegerSet.

hs
21set-language-deep.hs

Imports module SetLanguageDeep (or SetLanguageDeepCard) to demonstrate a deep embedding of the integer set DSL.

hs
22SetLanguageDeepCard.hs (module)

A deep embedding of IntegerSet. This module includes a cardinality observer for sets.

hs
23ExprDeep.hs (module)

A simple deeply embedded DSL over values of type Integer and Bool. Permits the construction of il-typed expressions.

hs
24expr-language.hs

Imports module ExprDeep and builds one well-typed and one ill-typed expression.

hs
25ExprDeepGADTTyped.hs (module)

Uses GADTs to define a deeply embedded DSL over Integer and Bool values that detects ill-typed expressions at compile time.

hs
26expr-language-typed.hs

Imports module ExprDeepGADTTyped and demonstrates the well-typed construction and evaluation of expressions.

hs
27round.hs

Builds on the fact that Either is an instance of Functor to build a composition of functions that propagates error messages.

hs
28stacked-functors.hs

Use a growing chain of fmap compositions to "reach into" and manipulate a complex value at desired depth.

hs
29break-the-law.hs

Defines a Functor instance for an algebraic data type and demonstrates that functor laws are satisfied/violated when we get the implementation of fmap right/wrong.

hs
30sequence-Maybe.hs

Defines the (>=>) left-to-right composition operator for partial functions of type a -> Maybe b and puts that to (simple) use.

hs
31sequence-Either.hs

Defines the (>=>) left-to-right composition operator for exception-generating functions of type a -> Exc ba -> Either Error b and puts that to (simple) use.

hs
32sequence-NonDet.hs

Defines the (>=>) left-to-right composition operator for non-deterministic functions of type a -> NonDet ba -> [b] and puts that to (simple) use.

hs
33sequence-ST.hs

Defines the (>=>) left-to-right composition operator for stateful functions of type a -> ST ba -> State -> (State, b) and puts that to (simple) use.

hs
34monadic-Maybe.hs

Define a composition based on partial functions a -> Maybe b based on the Monad instance for Maybe. Sequencing is based on monadic bind ((>>=)). Compare this to file sequence-Maybe.hs.

hs
35monadic-Either.hs

Composition of exception-generating functions (data types Either or Exc) in monadic style (using >>=).

hs
36monadic-ST.hs

Composition of state-transforming functions in monadic style.

hs
37monadic-NonDet.hs

Composition of non-deterministic functions in monadic style, using >>= and return explicitly.

hs
38monadic-do-NonDet.hs

Composition of non-deterministic functions in monadic style, using do-notation.

hs
39IOaction.hs

Demonstrates the separation of

  1. the pure construction of complex IO actions (type IOaction a) and
  2. the effectful execution of the constructed actions.

Construction uses monadic style to synthesize complex IO actions. A complex action essentially is a value of the algebraic data type IOaction a, i.e., an abstract syntax tree that describes a side-effectful program. Execution of the program is performed by Haskell's runtime system once function main returns the abstract syntax tree as its result.

hs
40normal-order.hs

Demonstrates that normal order reduction finds the normal form of an expression regardless of the presence of undefined values (function bomb has value ⊥).

hs
41sharing.hs

Uses trace (module Debug.Trace) to demonstrate that Haskell employs graph reduction (redex sharing) during evaluation.

hs
42bottom.hs

Demonstrates the strict semantics of pattern matching in Haskell.

hs
43min=head-isort.hs

Implements list minimum as the composition head . isort (<) to demonstrate that lazy evaluation (to WHNF) can make declarative specifications of algorithms efficient to execute.

Caveat: this depends on the interaction of head and isort and does not work for arbitrary sorting algorithms.

hs