Visitor Pattern, Algebraic Data Type & Catamorphism

class: center, middle

# Visitor Pattern, Catamorphism and Algebraic Data Type

Alexandre Bertails, Pellucid Analytics

[@bertails](http://twitter.com/bertails)

---

# constructing/evaluating expressions

`1 * 2 + 3` evaluates to `5`

---

# classes as tags for types

```scala
class Num(val n: Int)

class Sum(val l: Any, val r: Any)

class Prod(val l: Any, val r: Any)

object Expr {
  def eval(expr: Any): Int = expr match {
    case num: Num   => num.n
    case sum: Sum   => eval(sum.l) + eval(sum.r)
    case prod: Prod => eval(prod.l) * eval(prod.r)
  }
}

val expr =
  new Sum(new Prod(new Num(1), new Num(2)), new Num(3))

println(Expr.eval(expr)) // prints 5
```

---

# typesafe expressions

```scala
trait Expr

class Num(val n: Int) extends Expr

class Sum(val l: Expr, val r: Expr) extends Expr

class Prod(val l: Expr, val r: Expr) extends Expr

object Expr {
  def eval(expr: Expr): Int = expr match {
    case num: Num   => num.n
    case sum: Sum   => eval(sum.l) + eval(sum.r)
    case prod: Prod => eval(prod.l) * eval(prod.r)
  }
}

val expr =
  new Sum(new Prod(new Num(1), new Num(2)), new Num(3))

println(Expr.eval(expr)) // prints 5
```

---

# subtyping

```scala
trait Expr {
  def eval(): Int
}

class Num(val n: Int) extends Expr {
  def eval(): Int = n
}

class Sum(val l: Expr, val r: Expr) extends Expr {
  def eval(): Int = l.eval() + r.eval()
}

class Prod(val l: Expr, val r: Expr) extends Expr {
  def eval(): Int = l.eval() * r.eval()
}

val expr =
  new Sum(new Prod(new Num(1), new Num(2)), new Num(3))

println(expr.eval()) // prints 5
```

---

# visitor pattern as in GoF [1/2]

```scala
trait Expr {
  def accept(visitor: Visitor): Unit
}

class Num(val n: Int) extends Expr {
  def accept(visitor: Visitor): Unit = visitor.visit(this)
}

class Sum(val l: Expr, val r: Expr) extends Expr {
  def accept(visitor: Visitor): Unit = visitor.visit(this)
}

class Prod(val l: Expr, val r: Expr) extends Expr {
  def accept(visitor: Visitor): Unit = visitor.visit(this)
}

trait Visitor {
  def visit(num: Num): Unit
  def visit(sum: Sum): Unit
  def visit(prod: Prod): Unit
}
```

---

# visitor pattern as in GoF [2/2]

```scala
final class Eval() extends Visitor {
  var result: Int = 0
  def visit(num: Num): Unit = {
    result = num.n
  }
  def visit(sum: Sum): Unit = {
    sum.l.accept(this)
    val lresult = result
    sum.r.accept(this)
    val rresult = result
    result = lresult + rresult
  }
  def visit(prod: Prod): Unit = {
    prod.l.accept(this)
    val lresult = result
    prod.r.accept(this)
    val rresult = result
    result = lresult * rresult
  }
}

val expr =
  new Sum(new Prod(new Num(1), new Num(2)), new Num(3))
val statefulVisitor = new Eval()
expr.accept(statefulVisitor)
println(statefulVisitor.result) // prints 5
```

---

# visitor pattern with generics [1/2]

```scala
trait Expr {
  def accept[T](visitor: Visitor[T]): T
}

class Num(val n: Int) extends Expr {
  def accept[T](visitor: Visitor[T]): T = visitor.visit(this)
}

class Sum(val l: Expr, val r: Expr) extends Expr {
  def accept[T](visitor: Visitor[T]): T = visitor.visit(this)
}

class Prod(val l: Expr, val r: Expr) extends Expr {
  def accept[T](visitor: Visitor[T]): T = visitor.visit(this)
}

trait Visitor[T] {
  def visit(num: Num): T
  def visit(sum: Sum): T
  def visit(prod: Prod): T
}
```

---

# visitor pattern with generics [2/2]

```scala
final class Eval() extends Visitor[Int] {
  def visit(num: Num): Int = num.n
  def visit(sum: Sum): Int = sum.l.accept(this) + sum.r.accept(this)
  def visit(prod: Prod): Int = prod.l.accept(this) * prod.r.accept(this)
}

val expr =
  new Sum(new Prod(new Num(1), new Num(2)), new Num(3))

println(expr.accept(new Eval())) // prints 5
```

---

# visitor/catamorphism [1/2]

```scala
trait Expr {
  def accept[T](
    fnum: Num => T,
    fsum: Sum => T,
    fprod: Prod => T): T =
    this match {
      case num: Num   => fnum(num)
      case sum: Sum   => fsum(sum)
      case prod: Prod => fprod(prod)
    }
}

class Num(val n: Int) extends Expr

class Sum(val l: Expr, val r: Expr) extends Expr

class Prod(val l: Expr, val r: Expr) extends Expr
```

---

# visitor/catamorphism [2/2]

```scala
def eval(expr: Expr): Int = expr.accept(
  num  => num.n,
  sum  => eval(sum.l) + eval(sum.r),
  prod => eval(prod.l) * eval(prod.r)
)

val expr =
  new Sum(new Prod(new Num(1), new Num(2)), new Num(3))

println(eval(expr)) // prints 5
```

---

# algebraic data type

```scala
sealed trait Expr

case class Num(n: Int) extends Expr

case class Sum(l: Expr, r: Expr) extends Expr

case class Prod(l: Expr, r: Expr) extends Expr

def eval(expr: Expr): Int = expr match {
  case Num(n)     => n
  case Sum(l, r)  => eval(l) + eval(r)
  case Prod(l, r) => eval(l) * eval(r)
}

val expr =
  new Sum(new Prod(new Num(1), new Num(2)), new Num(3))

println(eval(expr)) // prints 5
```

---

# Option[A] data type

```scala
sealed trait Option[+A]

case class Some[+A](x: A) extends Option[A]

case object None extends Option[Nothing]

def flatten[T](oo: Option[Option[T]]): Option[T] = oo match {
  case None          => None
  case Some(None)    => None
  case Some(Some(x)) => Some(x)
}

assert(flatten(Some(Some(42))) == Some(42))

assert(flatten(Some(None)) == None)
```

---

# class hierarchy for Option[A]

.center[![Option class diagram](option.png)]

---

# deconstructing Scala case classes [1/2]

## existence of types & subtyping information

```scala
type OptionInt

type SomeInt <: OptionInt

type None <: OptionInt
```

---

# deconstructing Scala case classes [2/2]

## injectors

```scala
def some(x: Int): OptionInt

def none: OptionInt
```

## deconstructors

```scala
def fold[T](opt: OptionInt)(ifNone: => T, ifSome: Int => T): T
```

---

# abstracted case classes

```scala
trait OptionModule {

type OptionInt

type SomeInt <: OptionInt

type None <: OptionInt

def some(x: Int): OptionInt

def none: OptionInt

def fold[T](opt: OptionInt)(ifNone: => T, ifSome: Int => T): T

}
```

---

# building stuff on top of the abstraction

```scala
trait ShowOption extends OptionModule {

def show(opt: OptionInt): String = fold(opt)("None", x => s"Some($x)")

}
```

---

# OptionInt as visitor [1/2]

```scala
trait OptionVisitorModule extends OptionModule {

trait OptionInt {
    def accept[T](visitor: Visitor[T]): T
  }

class SomeInt(val x: Int) extends OptionInt {
    def accept[T](visitor: Visitor[T]): T = visitor.visit(this)
  }

class None() extends OptionInt {
    def accept[T](visitor: Visitor[T]): T = visitor.visit(this)
  }

trait Visitor[T] {
    def visit(none: None): T
    def visit(some: SomeInt): T
  }
```

---

# OptionInt as visitor [2/2]

```scala
  def some(x: Int): OptionInt = new SomeInt(x)

val none: OptionInt = new None()

def fold[T](opt: OptionInt)(ifNone: => T, ifSome: Int => T): T =
    opt.accept(new Visitor[T] {
      def visit(none: None): T = ifNone
      def visit(someInt: SomeInt): T = ifSome(someInt.x)
    })

}
```

---

# OptionInt as scala.class[.]Option[Int]

```scala
trait ScalaOptionModule extends OptionModule {

type OptionInt = scala.Option[Int]

type SomeInt = scala.Some[Int]

type None = scala.None.type

def some(x: Int): OptionInt = Some(x)

val none: OptionInt = scala.None

def fold[T](opt: OptionInt)(ifNone: => T, ifSome: Int => T): T = opt match {
    case scala.None    => ifNone
    case scala.Some(x) => ifSome(x)
  }

}
```

---

# using the abstraction

```scala
trait Program extends App with OptionModule with ShowOption {
  val opt = some(42)
  println(show(opt)) // will print Some(42)
}

object MainWithVisitor extends Program with OptionVisitorModule

object MainWithScalaOption extends Program with ScalaOptionModule
```

---

# modules as a cake (pattern) [1/3]

```scala
trait OptionModule {

type OptionInt

type SomeInt <: OptionInt

type None <: OptionInt

def Option: OptionLike

trait OptionLike {
    
    def some(x: Int): OptionInt
    
    def none: OptionInt
    
    def fold[T](opt: OptionInt)(ifNone: => T, ifSome: Int => T): T

}

}
```

---

# modules as a cake (pattern) [2/3]

```scala
trait ScalaOptionModule extends OptionModule {

type OptionInt = scala.Option[Int]

type SomeInt = scala.Some[Int]

type None = scala.None.type

object Option extends OptionLike {

def some(x: Int): OptionInt = Some(x)

val none: OptionInt = scala.None

def fold[T](opt: OptionInt)(ifNone: => T, ifSome: Int => T): T = opt match {
      case scala.None    => ifNone
      case scala.Some(x) => ifSome(x)
    }

}

}
```

---

# modules as a cake (pattern) [3/3]

```scala
trait ShowOption extends OptionModule {

object Show {
    def show(opt: OptionInt): String = Option.fold(opt)("None", x => s"Some($x)")
  }

}

trait Program extends App with OptionModule with ShowOption {
  val opt = Option.some(42)
  println(Show.show(opt)) // will print Some(42)
}

object MainWithScalaOption extends Program with ScalaOptionModule
```

---

# modules as a typeclass

## aka modules a la ML

```scala
trait OptionSig {

type OptionInt

type SomeInt <: OptionInt

type None <: OptionInt

}

trait OptionOps[Sig <: OptionSig] {

def some(x: Int): Sig#OptionInt
    
  def none: Sig#OptionInt
    
  def fold[T](opt: Sig#OptionInt)(ifNone: => T, ifSome: Int => T): T

}
```

---

# functors a la ML

```scala
class Show[Sig <: OptionSig](implicit ops: OptionOps[Sig]) {

import ops._

def show(opt: Sig#OptionInt): String = fold(opt)("None", x => s"Some($x)")

}
```

---

# implementations as typeclass instances

```scala
trait ScalaOption extends OptionSig {

type OptionInt = scala.Option[Int]

type SomeInt = scala.Some[Int]

type None = scala.None.type

}

object ScalaOption {

implicit object Ops extends OptionOps[ScalaOption] {
    def some(x: Int): ScalaOption#OptionInt = Some(x)
    val none: ScalaOption#OptionInt = scala.None
    def fold[T](opt: ScalaOption#OptionInt)(ifNone: => T, ifSome: Int => T): T =
      opt match {
        case scala.None    => ifNone
        case scala.Some(x) => ifSome(x)
      }
  }

implicit object Show extends Show[ScalaOption]

}
```

---

# programs as functors

```scala
class Program[Sig <: OptionSig](implicit Ops: OptionOps[Sig], Show: Show[Sig])
extends App {
  import Ops._
  import Show._
  val opt = some(42)
  println(show(opt)) // will print Some(42)
}

object MainWithScalaOption extends Program[ScalaOption]
```

---

# deriving functors automatically

```scala
class Show[Sig <: OptionSig](implicit ops: OptionOps[Sig]) {

import ops._

def show(opt: Sig#OptionInt): String = fold(opt)("None", x => s"Some($x)")

}

object Show {

def apply[Sig <: OptionSig](implicit ops: OptionOps[Sig]): Show[Sig] =
    new Show[Sig]

}

class Program[Sig <: OptionSig](implicit Ops: OptionOps[Sig]) extends App {
  import Ops._
  val S = Show[Sig]
  import S._
  val opt = some(42)
  println(show(opt)) // will print Some(42)
}

object MainWithScalaOption extends Program[ScalaOption]
```

---

# parameterized Option[A]

```scala
import scala.language.higherKinds

trait OptionSig {

type Option[+_]

type Some[+A] <: Option[A]

type None <: Option[Nothing]

}

trait OptionOps[Sig <: OptionSig] {

def some[A](x: A): Sig#Some[A]
    
  def none: Sig#None
    
  def fold[A, B](opt: Sig#Option[A])(ifNone: => B, ifSome: A => B): B

}
```

---

# Show functor

```scala
class Show[Sig <: OptionSig](implicit ops: OptionOps[Sig]) {

import ops._

// the type argument is provided on the call site
  def show[A](opt: Sig#Option[A]): String =
    fold(opt)("None", x => s"Some(${x.toString})")

}

object Show {

implicit def apply[Sig <: OptionSig](implicit ops: OptionOps[Sig]): Show[Sig] =
    new Show[Sig]

}
```

---

# Option[A] as scala.class[.]Option[A]

```scala
trait ScalaOption extends OptionSig {

type Option[+A] = scala.Option[A]

type Some[+A] = scala.Some[A]

type None = scala.None.type

}

object ScalaOption {

implicit object Ops extends OptionOps[ScalaOption] {

def some[A](x: A): ScalaOption#Some[A] = scala.Some(x)

val none: ScalaOption#None = scala.None

def fold[A, B](opt: ScalaOption#Option[A])(ifNone: => B, ifSome: A => B): B =
      opt match {
        case scala.None    => ifNone
        case scala.Some(x) => ifSome(x)
      }

}

}
```

---

# a program using Option[A]

```scala
class Program[Sig <: OptionSig](implicit Ops: OptionOps[Sig], Show: Show[Sig]) extends App {
  import Ops._
  import Show._
  val opt: Sig#Option[Int] = some(42)
  println(show(opt)) // will print Some(42)
}

object MainWithScalaOption extends Program[ScalaOption]
```

---

# Flatten functor

```scala
class Flatten[Sig <: OptionSig](implicit ops: OptionOps[Sig]) {

import ops._

def flatten[A](oo: Sig#Option[Sig#Option[A]]): Sig#Option[A] = fold(oo)(
    none,
    someOpt => fold(someOpt)(
      none,
      someA => some(someA)
    )
  )

}

object Flatten {

implicit def apply[Sig <: OptionSig](implicit ops: OptionOps[Sig]): Flatten[Sig] =
    new Flatten[Sig]

}
```

---

# using Flatten

```scala
class Program[Sig <: OptionSig](implicit Ops: OptionOps[Sig], Show: Show[Sig], Flatten: Flatten[Sig]) extends App {
  import Ops._
  import Show._
  println(show(Flatten.flatten(some(some(42))))) // will print Some(42)
}

object MainWithScalaOption extends Program[ScalaOption]
```

---

# enhanced syntax for Option[A]

how to write `myOption.flatten.show`?

```scala
class OptionW[Sig <: OptionSig, T](val opt: Sig#Option[T]) extends AnyVal {
  def show(implicit S: Show[Sig]): String = S.show(opt)
}

class OptionOptionW[Sig <: OptionSig, T](val oo: Sig#Option[Sig#Option[T]])
extends AnyVal {
  def flatten(implicit F: Flatten[Sig]): Sig#Option[T] = F.flatten(oo)
}

class Syntax[Sig <: OptionSig] {

implicit def optionW[T](opt: Sig#Option[T]): OptionW[Sig, T] =
    new OptionW[Sig, T](opt)

implicit def optOptW[T](oo: Sig#Option[Sig#Option[T]]): OptionOptionW[Sig, T] =
    new OptionOptionW[Sig, T](oo)

}

object Syntax {

implicit def apply[Sig <: OptionSig](implicit ops: OptionOps[Sig]): Syntax[Sig] =
    new Syntax[Sig]

}
```

---

# using Syntax

```scala
class Program[Sig <: OptionSig](implicit Ops: OptionOps[Sig], Syntax: Syntax[Sig])
extends App {
  import Ops._
  import Syntax._
  println(some(some(42)).flatten.show) // will print Some(42)
}

object MainWithScalaOption extends Program[ScalaOption]
```

<span>note</span>: no explicit instance of `Flatten[Sig]` or `Show[Sig]` needed

---

# Option[A] as java.class[.]util.class[.]Optional[A]

```scala
import java.util.Optional
import java.util.function.{ Function => F, Supplier }

trait Java8Option extends OptionSig {

type Option[+A] = Optional[_ <: A]

type Some[+A] = Optional[_ <: A]

type None = Optional[Nothing]

}

object Java8Option {

implicit object Ops extends OptionOps[Java8Option] {

def some[A](x: A): Java8Option#Some[A] = Optional.of(x)

val none: Java8Option#None = Optional.empty()

def fold[A, B](opt: Java8Option#Option[A])(ifNone: => B, ifSome: A => B): B = {
      def f = new F[A, B] { def apply(a: A): B = ifSome(a) }
      def supplier = new Supplier[B] { def get(): B = ifNone }
      opt.map[B](f).orElseGet(supplier)
    }

}

}
```

---

# Option[A] as Any and Null

```scala
trait NullOption extends OptionSig {

type Option[+A] = Any

type Some[+A] = Any

type None = Null

}

object NullOption {

implicit object Ops extends OptionOps[NullOption] {

def some[A](x: A): NullOption#Some[A] = x

val none: NullOption#None = null

def fold[A, B](opt: NullOption#Option[A])(ifNone: => B, ifSome: A => B): B = {
      if (opt == null)
        ifNone
      else
        ifSome(opt.asInstanceOf[A])
    }

}

}
```

---

# they all work the same way

```scala
class Program[Sig <: OptionSig](implicit Ops: OptionOps[Sig], Syntax: Syntax[Sig])
extends App {
  import Ops._
  import Syntax._
  println(Some(Some(42)).flatten.show) // will print Some(42)
}

object MainWithScalaOption extends Program[ScalaOption]

object MainWithJava8Option extends Program[Java8Option]

object MainWithNullOption extends Program[NullOption]
```

---

# sources

Code at https://github.com/betehess/talks/tree/gh-pages/2014/06/cata-visitor-adt

* typecasting.scala
* typecasting2.scala
* subtyping.scala
* visitor-state.scala
* visitor-generics.scala
* visitor-cata.scala
* pattern-matching.scala
* option-pattern-matching.scala
* option-abstraction.scala
* option-cake.scala
* option-typeclass.scala
* option-typeclass2.scala
* option-parameterized.scala
* option-flatten.scala
* option-syntax.scala
* option-impls.scala

Slides at http://betehess.github.io/talks/2014/06/06-cata-visitor-adt.html

---

# Some links

* http://merrigrove.blogspot.com/2011/12/another-introduction-to-algebraic-data.html

* http://logji.blogspot.com/2012/02/correcting-visitor-pattern.html