Section 10

Algebraic Data Type

It is a kind of composite type, which means it is formed by combining other types. Two main classes of algebraic data type are product types and sum types.

Product Types

The values of this type typically contain several values/fields. e.g. tuple type, record type. It is called "product" because the set of values of a product type, is the set-theory product of all values of its fields. e.g. the set of values of this tuple (int, bool) is formed by computing Cartesian product of {all integers} * {all boolean values}.

Sum Types

The values of this type are typically grouped into different variants. Those possible values of a variants is defined by its corresponding constructor. It is called sum type because the values of a sum type is a union/sum of values of those variants.

Pattenr Matching

It is used to identify a value by its constructor or field name.

Examples

data Tree = Empty
    | Leaf Int
    | Node Tree Tree

Here, we are defining a data type called Tree, and its possible values are splited into three different variants, which are defined by three constructors Empty, Leaf and Node. Empty takes no parameter and generates a value of type Tree. It carries no data. Leaf takes an integer, and returns a value of type Tree. It carries one piece of data of type integer. Node takes two values of type Tree itself, and return another value of type Tree. It takes two pieces of data of type Tree, and it is recursive.

When building a value of Tree, we are carring data by using constructors. We can later retrieve those data by destructing them, which is exactly the pattern matching mentioned in the lecture. By matching, we know which variant the value belongs to, therefore we know which constructor is used to build that value, and further more we know what data is carried by this constructor.

depth :: Tree -> Int
depth Empty = 0
depth (Leaf n) = 1
depth (Node l r) = 1 + max (depth l) (depth r)

And you can think of that as

int depth (Tree data) {
    switch (data.constructor) {
        case Empty:
            return 0;
        case Leaf:
            int n = data.field1
            return 1;
        case Node:
            int l = data.field1
            int r = data.field2
            return 1 + max (depth (l), depth (r));
    }
}

Excerise

  1. Define a single linked list.
  2. Define a function that get the n-th element of that list.
  3. Define a function that reverse the list.
data List = Nil
          | Cons Int List
          deriving Show

list_len :: List -> Int
list_len (Nil) = 0
list_len (Cons _ l) = 1 + list_len (l)

list_get :: (List, Int) -> Int
list_get ((Cons d _), 1) = d
list_get ((Cons _ l), n) = list_get (l, (n - 1))

list_reverse :: List -> List 
list_reverse_do :: (List, List) -> List
list_reverse (l) = list_reverse_do (l, Nil)
list_reverse_do (Nil, l) = l
list_reverse_do (Cons a l, b) = list_reverse_do (l, Cons a b)