Algebraic Data Types

We've used algebraic data types throughout Creative Scala, but we've been a bit informal in how we describe them. At this stage a bit more rigour is useful.

An algebraic data type is built from two components: - logical ors; and - logical ands.

The List data type is a great example of an algebraic data type, as it uses both patterns. A List is Nil or a pair (the logical or pattern) and a pair has a head and a tail (the logical and pattern). Point is another example. A Point is either Cartesian or Polar. A Cartesian has an x and y coordinate, while a Polar has a radius and an angle. Note it's not necessary to use both patterns to be an algebraic data type.

Being functional programmers we naturally have some fancy words for the logical or and logical and patterns. They are: - a sum type for the logical or; and - a product type for the logical and.

The concept of an algebraic data type is not specific to Scala. Let's get some practice working with the concept before we see how to write algebraic data types in Scala.

Exercises {-}

Path Elements {-}

The PathElement type, used to construct paths, is a simple algebraic data type. You've used PathElement quite a bit so far. How do you think PathElement is defined in terms of sum and product types?

<div class="solution"> A PathElement is a sum type, as it is: - a MoveTo; or - a LineTo; or - a CurveTo.

A MoveTo is a product type that holds a single point (where to move to).

A LineTo is a product type that holds a single point (the end point of the line).

A CurveTo is a product type that holds three points: two control points and the end point of the line. </div>

Totally Turtles {-}

The Instruction type we used to control the turtle is also an algebraic data type. How do you think Instruction is defined?

<div class="solution"> An Instruction is: - a Forward; or - a Turn; or - a Branch; or - a NoOp

Therefore Instruction is a sum type. Forward, Turn, and Branch are all product types.

A Forward holds a distance, which is a Double.

A Turn holds an angle, which is an Angle.

A Branch holds a List[Instruction]---therefore the Instruction type is defined in terms of itself, just like List.

A NoOp holds no data. </div>

Defining Algebraic Data Types

No we understand how to model data with algebraic data types, let's see how to define our own.

The pattern is this:

sealed abstract class A extends Product with Serializable
final case class B() extends A
final case class C() extends A

There is a lot boilerplate here, which we can basically ignore beyond accepting it's stuff we have to write. However, if you're interested in what it means (and possibly have some prior object-oriented programming experience).

<div class="info-warning"> Describe sealed etc. here. </div>

To define PathElement we might start with

sealed abstract class PathElement extends Product with Serializable
final case class MoveTo() extends PathElement
final case class LineTo() extends PathElement
final case class CurveTo() extends PathElement

The other half of the pattern is

final case class A(b: B, c: C)

<div class="info-warning"> Describe constructor parameters here. </div>

Returning to PathElement, MoveTo and LineTo each have a point (the destination) and CurveTo has a destination point and two control points. So we could write.

sealed abstract class PathElement extends Product with Serializable
final case class MoveTo(to: Point) extends PathElement
final case class LineTo(to: Point) extends PathElement
final case class CurveTo(cp1: Point, cp2: Point, to: Point) extends PathElement

And this is essentially how PathElement is defined in Doodle.

Exercise {-}

Define your own algebraic data type to represent Instruction.

<div class="solution"> We can directly turn the textual description into code using the patterns above.

sealed abstract class Instruction extends Product with Serializable
final case class Forward(distance: Double) extends Instruction
final case class Turn(angle: Angle) extends Instruction
final case class Branch(instructions: List[Instruction]) extends Instruction
final case class NoOp() extends Instruction

</div>