Comparing revisions for page Functional data structures

  == Headline ==

Functional data structures in Haskell

== Description ==

We look at functional programming techniques for implementing abstract data types and concrete data structures. In particular, we want to get a basic understanding of using familiar data types such as stacks or heaps without relying on side effects and thereby providing a form of persistence. To this end, we leverage so-called functional data structures which exploit (path) copying to achieve persistence while potentially leveraging lazy evaluation to achieve competitive performance (complexity).

== Material ==





== Concepts ==

* [[Stack]]
* [[A functional data structure is a persistent data structure which is implemented in a functional style. Such data structures involve (path) copying to achieve persistence and they may rely on lazy evaluation to achieve competitive performance (complexity).

== Material ==





== Conceptstract ==

* [[Lazy evaluation]]
* [[Functional data type]]
* [[Lazy evaluation]]
* [[Functional data structure]]
* [[Stack]]
* [[Binary search tree]]
* [[Skew heap]]
* [[Amortized analysis]]

== Further reading ==

* [[Document:Handbook of data structures and applications]]
* [[Document:Okasaki96]]
* [https://github.com/101companies/101repo/tree/master/concepts/Functional_data_structure]

== Metadata ==

* [[memberOf::Course:Lambdas in Koblenz]]
* [[dependsOn::Script:Higher-order functions in Haskell]]