4 Programming in Curry

4.1 Overview

Lists and trees are datatypes frequently used in programming.

  • A list abstracts a sequence of elements. The elements of a list are implicitly ordered by the list structure. Therefore, a list is a convenient representation for queues, stacks and other linear structures. As list can also be used for representing collections, typically unordered, such as a set, by ignoring or hiding the implicit order of the elements.

  • A tree is a multibranching data structure that abstracts a hierarchy of values or conditions. It naturally represents taxonomies or classifications and therefore it is useful for problems involving search. Trees come in many variants, but all consists of a value called root and some subtrees called children. Similar to lists, trees can be used for representing collections.

This section describes in some detail both these datatypes and how they help solve some typical problems, e.g., sorting a collection of elements or searching for an element in a collection.