Skip to content
Snippets Groups Projects
progfun1-4-3.md 4.43 KiB
Newer Older
% Algebraic Data Types
Martin Odersky's avatar
Martin Odersky committed
%
%
Algebraic Data Types
====================
Martin Odersky's avatar
Martin Odersky committed

We have seen how heterogenous data is described by a hierarchy of case classes and objects.
Martin Odersky's avatar
Martin Odersky committed

Defining new data types is quite common in statically typed functional languages, so there exists
a shorthand for it.
Martin Odersky's avatar
Martin Odersky committed

The shorthand generalizes the `enum` syntax we have seen earlier.
Example
=======
Martin Odersky's avatar
Martin Odersky committed

~~~
  enum Student {
    case Listening
    case Asking(question: String)
  }
~~~
Martin Odersky's avatar
Martin Odersky committed

 - This definition introduces a `Student` type consisting of two cases, `Listening` and `Asking`.
 - The `Asking` case is parameterized with a value parameter `question`.
 - Since `Listening` is not parameterized, it is treated as a normal enum value.
Matching on Constructors
========================
Martin Odersky's avatar
Martin Odersky committed

Since `Asking` is not a constant, we match on it using a _constructor pattern_
Martin Odersky's avatar
Martin Odersky committed

~~~
  student match
    case Student.Listening => "Student is listening"
    case Student.Asking(q) => s"Student is asking: $q"
~~~
Martin Odersky's avatar
Martin Odersky committed

A constructor pattern allows us to _extract_ the value of
the `question` parameter, in case the `student` value is
indeed of type `Asking`.
Martin Odersky's avatar
Martin Odersky committed

Here, the `q` identifier is bound to the `question` parameter
of the `student` object.
Martin Odersky's avatar
Martin Odersky committed

Relationship With Case Classes
==============================
Martin Odersky's avatar
Martin Odersky committed

Algebraic Data types expand to class hierarchies with case classes.
Martin Odersky's avatar
Martin Odersky committed

For instance, the `Student` type expands to something like:
Martin Odersky's avatar
Martin Odersky committed

~~~
  abstract class Student
  object Student {
    val Listening extends Student
    case class Asking(question: String) extends Student
  }
~~~
Martin Odersky's avatar
Martin Odersky committed

Comparison With Object Oriented Decomposition
=============================================
Martin Odersky's avatar
Martin Odersky committed

OO decomposition and algebraic data types are two ways of defining types and operations.
Martin Odersky's avatar
Martin Odersky committed

When should you use one or the other?
Martin Odersky's avatar
Martin Odersky committed

Use an algebraic data type to model
Martin Odersky's avatar
Martin Odersky committed

 - a type with a fixed number of alternatives, where
 - all alternatives are pure data types that do not contain methods.
Martin Odersky's avatar
Martin Odersky committed

Use a hierarchy with classes, if
Martin Odersky's avatar
Martin Odersky committed

 - The set of alternatives is open, i.e. new alternatives can be added after the fact, or
 - Alternatives are complex, consisting of methods as well as parameters.
Martin Odersky's avatar
Martin Odersky committed

Enumerations Can Be Recursive
=============================
Martin Odersky's avatar
Martin Odersky committed

A list of integer values can be modeled as either an empty list,
or a node containing both a number and a reference to the remainder
of the list.
Martin Odersky's avatar
Martin Odersky committed

~~~
  enum List {
    case Empty
    case Node(value: Int, next: List)
  }
~~~
Martin Odersky's avatar
Martin Odersky committed

A list with values `1`, `2`, and `3` can be constructed as follows:
Martin Odersky's avatar
Martin Odersky committed

~~~
List.Node(1, List.Node(2, List.Node(3, List.Empty)))
~~~
Martin Odersky's avatar
Martin Odersky committed

Examples of Lists
=================
     List(1, 2, 3)
     List(List(true, false), List(3))
Martin Odersky's avatar
Martin Odersky committed

Exercise: Arithmetic Expressions
================================
Martin Odersky's avatar
Martin Odersky committed

Define an algebraic datatype modeling arithmetic expressions.
Martin Odersky's avatar
Martin Odersky committed

An expression can be:
Martin Odersky's avatar
Martin Odersky committed

- a number (e.g. `42`),
- a sum of two expressions,
- or, the product of two expressions.
Martin Odersky's avatar
Martin Odersky committed

`Expr` Type Definition
====================
Martin Odersky's avatar
Martin Odersky committed

~~~
  enum Expr {
    case Number(n: Int)
    case Sum(lhs: Expr, rhs: Expr)
    case Prod(lhs: Expr, rhs: Expr)
  }
~~~
\begin{tabular}{ll}
 \verb@val one = Expr.Number(1)@  \wsf one: Expr = Number(1) \\
 \verb@val two = Expr.Number(2)@  \wsf two: Expr = Number(2) \\
 \verb@Expr.Sum(one, two)@        \wsf Sum(Number(1), Number(2))
\end{tabular}
Martin Odersky's avatar
Martin Odersky committed

Exercise
========

Is the following match expression valid?
Martin Odersky's avatar
Martin Odersky committed

~~~
expr match {
  case Expr.Sum(x, x) => Expr.Prod(2, x)
  case e              => e
}
~~~
Martin Odersky's avatar
Martin Odersky committed

     O         Yes
     O         No
Martin Odersky's avatar
Martin Odersky committed

Exercise
========
Martin Odersky's avatar
Martin Odersky committed

Implement an `eval` operation that takes an `Expr` as parameter and
evaluates its value:
Martin Odersky's avatar
Martin Odersky committed

~~~
def eval(e: Expr): Int
~~~
Martin Odersky's avatar
Martin Odersky committed

Examples of use:
Martin Odersky's avatar
Martin Odersky committed

\begin{tabular}{ll}
 \verb@eval(Expr.Number(42))@  \wsf 42 \\
 \verb@eval(Expr.Prod(2, Expr.Sum(Expr.Number(8), Expr.Number(13))))@  \wsf 42
\end{tabular}
Martin Odersky's avatar
Martin Odersky committed

Exercise
========

Implement a `show` operation that takes an `Expr` as parameter and
returns a `String` representation of the operation.
Martin Odersky's avatar
Martin Odersky committed

Be careful to introduce parenthesis when necessary!
Martin Odersky's avatar
Martin Odersky committed

~~~
def show(e: Expr): String
~~~
Martin Odersky's avatar
Martin Odersky committed

Examples of use:
Martin Odersky's avatar
Martin Odersky committed

\begin{tabular}{ll}
 \verb@show(Expr.Number(42))@  \wsf "42" \\
 \verb@show(Expr.Prod(2, Expr.Sum(Expr.Number(8), Expr.Number(13))))@  \wsf "2 * (8 + 13)"
Martin Odersky's avatar
Martin Odersky committed
\end{tabular}

Summary
=======

In this lecture, we have seen:

- how to define data types accepting alternative values using
  `enum` definitions,
- enumeration cases can be discriminated using pattern matching,
- enumeration cases can take parameters or be simple values,
- pattern matching allows us to extract information carried by an object.