Title | Seminar: Functional Data Structures and Algorithms |

Term | Winter 2017/18 |

Dates: | 4.12., 11.12., 18.12., each 14:00–17:00 in 00.09.038 |

Module type | Bachelor's seminar (IN0014), Master's seminar (IN2107) |

Prerequisites | Functional Data Structures (IN2347) |

SWS | 2 |

ECTS | 4 |

Organisation | Mohammad Abdulaziz, Manuel Eberl, Lars Hupel, Tobias Nipkow |

Every participant will receive a topic about which they will write a written paper and give a presentation to the other participants. Also, every participant will be required to give a short written review of the papers of two other participants. The precise schedule will be made available below.

The presentations will be held in sessions of 2 – 3 talks each during the semester, each 14:00–17:00 in Seminar Room 00.09.038 (Alan Turing).

- Session 1, 4 December 2017
- Martin Wauligmann, Matrices

- Session 2, 11 December 2017
- Fabio Madge Pimentel, Finger Trees
- Shuwei Hu, Zippers
- Fabian Hellauer, Regular Expression Equivalence via Derivatives

- Session 3, 18 December 2017
- Julian Erhard, Lenses
- Roland Schmid, Priority Search Queues

The seminar can be attended as either a Bachelor's or Master's seminar. Each topic below indicates for which of the two it is intended. Some topics are suitable both for the Bachelor's and Master's seminar; however, for the Master's seminar, the students are supposed to cover the topic in more depth.

Participants must hand in

- a complete (!) paper draft
**three weeks**before their presentation to**both**Manuel Eberl and their advisor; this will be reviewed by other students - a draft version of their presentation slides to their advisor
**one week**before their talk - the final versions of their paper and presentatio to
**both**Manuel Eberl and their advisor on the day of the presentation. - reviews of two papers they were assigned within
**one week**before the respective presentation to Manuel Eberl

- The length of the paper should be roughly 10 pages.
- The length of the talk between 35 and 45 minutes (excluding Q&A session) and must
**not**exceed 45 minutes. - Reviews, presentations, and papers should be in English.
- There are no strict requirements on the form of the paper or slides. No template will be provided.
- All submissions are to be sent to Manuel Eberl.

- Reviewers receive the drafts of their assigned topics as soon as they are handed in.
- The main focus of the reviews should be the
*content*and the*presentation*of the papers. Does it make sense? Is it well-structured? Is it understandable to someone who has not read the source material? - Reviewers are not expected to read the cited source material.
- Spelling and grammar may also be mentioned, but are less important.
- A summary of the reviewed topic is
*not*required. - Reviews should be roughly one page long
- Reviewers may freely decide whether to use full sentences or bullet points.

The following list is preliminary and will be extended soon.

**Description:** Zippers facilitate moving through a data structure (such as a list or a tree). With a zipper, it is e.g. possible to denote a certain position in a tree while modifying its values. There is an interesting correspondence between between zippers of algebraic data types and formal derivatives and combinatorial species, which is to be illustrated informally in the talk.

**References:** Zippers: [1] Functional Pearls: The Zipper [PDF], Derivatives: [2] The Derivative of a Regular Type is its Type of One-Hole Contexts [PDF]

**Type:** Bachelor Seminar, possibly Master Seminar if more focus is put on combinatorial species.

**Advisor:** Manuel Eberl

**Description:** The goal of this master topic is to describe the general purpose data structure of finger trees, its properties, and applications.

**References:** [1] Finger Trees: A Simple General-Purpose Data Structure

**Prerequisites:** (Basic) Knowledge of functional programming language, knowledge of at least one search-tree data structure (e.g., AVL-tree, RB-tree, 2,3-tree, ...)

**Type:** Master Seminar

**Advisor:** Julian Brunner

**Description:** The student introduces and explains the technique of implicit recursive slowdown, demonstrates the technique using a concrete data structure (e.g., double-ended queues) and discusses the complexity and difference between functional and procedural implementation. A different topic from the book is also possible after a consultation with the advisor.

**References:** [1] Chris Okasaki: Purely Functional Data Structures [read online (may require eAccess)]

**Type:** Bachelor Seminar

**Advisor:** Ondřej Kunčar

**Description:** The student introduces the technique of amortization and shows how to eliminate it (Chapter 5 in [1]). Demonstration on concrete data structures is expected.

**References:** [1] Chris Okasaki: Purely Functional Data Structures [read online (may require eAccess)]

**Type:** Bachelor Seminar

**Advisor:** Fabian Immler

**Description:** Priority search queues are a blend of finite maps (or dictionaries) and priority queues, that is, they support both dictionary operations (for instance, accessing a binding with a given key) and priority queue operations (for instance, accessing a binding with the minimum value).

**References:** [1]

**Type:** Master Seminar

**Advisor:** Tobias Nipkow

**Description:** HAMTs are implementations of dictionaries, behaving similarly to hash
tables. Internally, they use a trie-like structure. Ideal Hash Trees are
the persistent variant of HAMTs, described by Phil Bagwell [1].
Currently, many functional programming languages, including Clojure and
Scala, use Ideal Hash Trees as their default implementation of maps [2].

**References:** [1] [2]

**Type:** Bachelor or Master

**Advisor:** Lars Hupel

**Description:**
Lenses, or "functional references", or "first-class labels" are a common
concept in functional programming. They are used to deal with immutable
data structures. In the simplest definition, a lens is a pair of a
setter and a getter function. A getter function retrieves the value of a
field in a record, whereas a setter function changes the value of a
field, returning the updated record. What's nice about lenses is that
they compose: If you have a lens for X in Y, and a lens for Y in Z, you
can obtain a lens for X in Z. There's a multitude of resources on the
web about lenses [1]. I recommend going through this overview on Stack
Overflow [2] and a survey paper [3] first.

**References:** [1] [2] [3]

**Type:** Bachelor or Master

**Advisor:** Lars Hupel

**Description:** Comparing functional representations of matrices like quad-trees and the encoding of shape invariants in the type [1].
Discuss common algorithms on those data structures.

**References:**

[1] Chris Okasaki. From Fast Exponentiation to Square Matrices: An Adventure in Types.

[2] David S. Wise. Matrix algorithms using quadtrees.

**Type:** Bachelor or Master

**Advisor:** Fabian Immler

**Description:** This paper describes a functional decision procedure for equivalence of regular expressions based on the notion of derivative of a regular expression.

**References:** [1]

**Type:** Master

**Advisor:** Tobias Nipkow

- Applications must be made through the Matching platform.
**You must have attended the Functional Data Structures lecture to be allowed to participate in the seminar.**- The allocation of topics to the participants will be done by us according to the preferences given by the participants.
- Each participant will be assigned two other topics to review. Reviewers can choose to remain anonymous.
- There will be no kick-off meeting. If you have any questions about the seminar or the topics, send an email to Manuel Eberl.

Services like Google Scholar can be useful to find relevant scientific papers for your topic. Afterwards, you can gain access to these publications using the university's eAccess. This step is necessary because scientific publisher's often demand high prices for the publications otherwise.