Scala Algebraic Datatypes

Peano Natural Numbers

Peano natural numbers: defined as base case \(0\) or a transitive successor of it

Algebraic Datatype PeanoNat

Mixes case object (Zero) and case class Succ.

enum PeanoNat:
  case Zero
  case Succ(n: PeanoNat)

Evaluate to a Number

Evaluate PeanoNat to Int

import PeanoNat.*
def peano2int (p: PeanoNat, result: Int = 0): Int = p match 
  case Zero    => result
  case Succ(n) => peano2int (n, result+1) // tail-recursive

Create an instance and evaluate

val q = Succ(Succ(Succ(Zero))) // val q: Peano = ...
peano2int(q) // : Int = 3

Linked List

Algebraic Datatype

enum IntList:
  case Empty
  case Cons (head: Int, tail: IntList)
end IntList

Length of List

def length (xs: IntList): Int = xs match 
  case IntList.Empty      => 0
  case IntList.Cons(_,as) => 1 + length(as)

Create a list and compute length

import IntList.*
val xs = Const(1, Cons(2, Cons(3, Empty))) // val xs: IntList = ...
length(xs) // : Int = 3

Binary Tree with Arithmetic Operations

Algebraic Datatype

enum Tree[X]:
  case Leaf (data: X)
  case Node (l: Tree[X], f: (X,X)=>X, r: Tree[X])

Evaluate the Tree by Applying all Operations

Evaluate recursive with pattern matching

def fold [X] (t: Tree[X]) : X = t match 
  case Leaf(x) => x
  case Node(l, f, r) => f(fold(l), fold(r))

Create an instance and evaluate

      *
     / \
    /   \
   /     \
  +       -
 / \     / \
1   2   +   5
       / \
      3   4
val t = Node(Node(Leaf(1), _ + _, Leaf(2)), 
             _ * _ , 
             Node(Node(Leaf(3), _ + _, Leaf(4), 
                  _ - _, 
                  Leaf(5))))
fold(t) // : Int = 6