Systematic processes are …

Consistent

Scalable

Save Time

What if (Scala) programming could be systematic? (A science?)

Consistent code = readable code

Juniors more productive

Better separation between levels of abstraction

Programming strategies

Demonstrate 5 strategies

Build a stream processing system (like FS2, Monix, etc.)

What’s a Stream?

Huge literature

A Stream is like a List

(where data is ordered by time, instead of space)

A Stream is like a List

Many APIs are algebraic.

// Introduction forms
def fromIterator: Iterator[A] => Stream[A]

// Combinators
def map: Stream[A] => (A => B) => Stream[B]

// Elimination forms
def run: Stream[A] => (B, (B, A) => B) => B

plus laws

How do we implement the ???s?

trait Stream[A] {
  def map[B](f: A => B): Stream[B] = ???
  def zip[B](that: Stream[B]): Stream[(A,B)] = ???
  def flatMap[B](f: A => Stream[B]): Stream[B] = ???
  def run[B](zero: B)(f: (B, A) => B): B = ???
}

object Stream {
  def fromIterator[A](source: Iterator[A]): Stream[A] =
    ???
}

Reification

sealed trait Stream[A] {
  ...
  def map[B](f: A => B): Stream[B] = Stream.Map(this, f)
  ...
}

object Stream {
  ...
  final case class Map[A,B](source: Stream[A], f: A => B) extends Stream[B]
  ...
}

Reification

sealed trait Stream[A] {
  import Stream._

  def map[B](f: A => B): Stream[B] = Map(this, f)
  def zip[B](that: Stream[B]): Stream[(A,B)] = Zip(this, that)
  def flatMap[B](f: A => Stream[B]): Stream[B] = FlatMap(this, f)
  def run[B](zero: B)(f: (B, A) => B): B = ???
}

object Stream {
  final case class Map[A,B](source: Stream[A], f: A => B) extends Stream[B]
  final case class Zip[A,B](left: Stream[A], right: Stream[B]) extends Stream[(A,B)]
  final case class FlatMap[A,B](source: Stream[A], f: A => Stream[B]) extends Stream[B]
  final case class FromIterator[A](source: Iterator[A]) extends Stream[A]
  
  def fromIterator[A](source: Iterator[A]): Stream[A] =
    FromIterator(source)
}

Reification

how do we run it?

def run[B](zero: B)(f: (B, A) => B): B = ???

Interpreter

Structural Recursion

def run[B](zero: B)(f: (B, A) => B): B = {
  def loop[C](stream: Stream[C])(zero: B)(f: (B, C) => B): B =
    stream match {
      case Map(s, f2) => ???
      case Zip(l, r) => ???
      case FlatMap(s, f2) => ???
      case FromIterator(s) => ???
    }
    
  loop(this)(zero)(f)
}

Structural Recursion

how do we implement the ???s?

def run[B](zero: B)(f: (B, A) => B): B = {
  def loop[C](stream: Stream[C])(zero: B)(f: (B, C) => B): B =
    stream match {
      case Map(s, f2) => ???
      case Zip(l, r) => ???
      case FlatMap(s, f2) => ???
      case FromIterator(s) => ???
    }
    
  loop(this)(zero)(f)
}

Structural Recursion

Follow the Types

def run[B](zero: B)(f: (B, A) => B): B = {
  def loop[C](stream: Stream[C])(zero: B)(f: (B, C) => B): B =
      stream match {
        case Map(s, f2) => loop(s)(zero)((b, d) => f(b, f2(d)))
        case Zip(l, r) => ???
        case FlatMap(s, f2) => ???
        case FromIterator(s) => ???
      }
      
    loop(this)(zero)(f)
}

Follow the Types

def run[B](zero: B)(f: (B, A) => B): B = {
  def loop[C](stream: Stream[C])(zero: B)(f: (B, C) => B): B =
    stream match {
      case Map(s, f2) => loop(s)(zero)((b, d) => f(b, f2(d)))
      case Zip(l, r) => loop(l)(zero)((b, d) => 
          loop(r)(zero)((b, e) => f(b, (d, e)))
        )
      case FlatMap(s, f2) => loop(s)(zero)((b, d) => loop(f2(d))(zero)(f))
      case FromIterator(s) => s.foldLeft(zero)(f)
    }
    
  loop(this)(zero)(f)
}

Semantics of Strategies

operational

vs.

denotational

Read the Literature: great artists steal

sealed trait Stream[A] {
  def map[B](f: A => B): Stream[B] = ???
}

Algebraic Data Types: ANDs and ORs

sealed trait Shape

case class Circle(radius: Double) extends Shape
case class Rect(height: Double, width: Double) extends Shape

Structural Recursion: transform ADTs

sealed trait Shape {
  def draw(): Unit =>
    this match {
      case Circle(r) => ???
      case Rect(h, w) => ???
    }
}

Sequencing: what must happen after something else, and what things can happen at the same time.

Applicative & Monad

Interpreters: separate what from how

Type Classes: ad-hoc polymorphism

Thank you!

Adam Rosien @arosien

Inner Product LLC inner-product.com

Hire us to teach your team! ☝︎

Special thanks to Noel Welsh for his hard work in codifying these strategies.

• How to draw a doge
• How to draw an Australian Masked Owl