Skip to content

Latest commit

 

History

History
433 lines (338 loc) · 8.21 KB

building.org

File metadata and controls

433 lines (338 loc) · 8.21 KB

Building A Program

About Me

Bill Carlson

Cotiviti Labs

The Bungalow

Last Time in “Functional Programming”

  • Programming with functions
  • Referential transparency

A program is evaluated by repeated substitution of function calls with the values they represent.

The code is simply an interpreter for a particular algebra. The program is the data that gets evaluated.

But how do you actually build the program?

Data Types Revisited

Standard Types

  • Int
  • String

Higher-Kinded Types

  • Option[A]
  • List[A]
  • Either[E, A]

Typeclasses

Typeclasses

  • Typeclasses are a mechanism to allow for ad-hoc polymorphism
  • The typeclass declares an interface
  • THe instance defines the operations

Typeclasses allow you to modify behavior of code you don’t own.

Typeclasses

trait Show[A] { 
  def show(a: A): String
}
implicit val stringShow = new Show[String] {
  def show(s: String) = s
}
implicit val addressShow = new Show[Address] {
  def show(addr: Address) = 
    s"""|${addr.street}
        |${addr.city} ${addr.state} ${addr.zip}""".stripMargin
}

Typeclasses

// A polymorphic function that works only when there is an implicit 
// instance of Show[A] available
def log[A](a: A)(implicit s: Show[A]) = println(s.show(a))
object Show { 
  def apply[A] = implicitly[Show[A]]
}
def log[A : Show](a: A) = println(Show[A].show(a))

Algebraic Combinators

Monoid

trait Monoid[A] { 
  val zero: A
  def append(a: A, b: A)): A
}

String concatenation

val stringConcat = new Monoid[String] { 
  val zero: String = ""
  def append(a: String, b: String)) = a + b
}

Integer Addition

val additionMonoid = new Monoid[Int] { 
  val zero: Int = 0
  def append(a: Int, b: Int)) = a + b
}

Integer Multiplication

val multiplicationMonoid = new Monoid[Int] { 
  val zero: Int = 1
  def append(a: Int, b: Int)) = a * b
}

Laws

Right Identity

append(a, zero) == a

Left Identity

append(zero, a) == a

Associativity

append(a, append(b, c)) === append(append(a, b), c)

Option

def optionMonoid[A : Monoid] = new Monoid[Option[A]] { 
  val zero: Int = None
  def append(a: Option[A], b: Option[A])) = a match { 
    case None => b
    case Some(x) => b match { 
      case None => a
      case Some(y) => Some(implicitly[Monoid[A]].append(x, y))
    }
  }
}

optionMonoid[Int].append(Some(3), Some(4)) == Some(7)
optionMonoid[Int].append(Some(3), None) == Some(3)

Foldable

trait Foldable[F[_]] {
  def foldLeft[A, B](a: F[A])(z: B)(f: (B, A) => B): B
  def foldRight[A, B](a: F[A])(z: B)(f: (A, B) => B): B
  def foldMap[A, B : Monoid](a: F[A])(f: A => B): B = 
    foldLeft(a)(Monoid[B].empty) { (b, a) => 
      Monoid[B].append(b, f(b))
    }
}

Combine

def combine[F[_], A : Monoid](a: F[A]): A = 
  Foldable[F].foldMap(a)(identity)

combine(List(1, 2, 3, 4)) // 10
combine(List("how", "now", "brown", "cow")  // "hownowbrowncow"

Count

def count[F[_], A : Monoid](a: F[A]): A = 
  Foldable[F].foldMap(a)(_ => 1)

count(Some(4)) // 1
count(None)    // 0
count(List(1,2,3,4)) // 4

Functor

trait Functor[F[_]] { 
  def map[A, B](a: F[A], f: A => B): F[B]
}

Which means?

map allows you to modify the values within a context without modifying the shape of the context

What does that mean?

Functor[Option].map(Some(4), (_: Int) * 2) === Some(8)
Functor[Option].map(None, (_: Int) * 2) === None
Functor[List].map(List(1, 2, 3, 4), (_: Int) * 2) === List(2, 4, 6, 8)
Functor[List].map(List.empty[Int], (_: Int) * 2) === List()

Laws

Identity

F.map(a)(identity) == a

Composition

F.map(F.map(a)(f))(g) == F.map(a)(f compose g)
a.map(f).map(g) == a.map(f andThen g)

Applicative

Because not every function has one argument…

What happens if you have a function

f: (A, B) => C
Functor[Option].map(Some(3), f)
// error: type mismatch;
//  found   : (Int, Int) => Int
//  required: Int => ?
f.curried // (a: Int) => (b: Int) => f(a, b)
Functor[Option].map(Some(3), f.curried)
// Some[Int => Int]

Applicative

trait Apply[F[_]] { 
  def ap[A, B](a: F[A], b: F[A => B]): F[B]
}
val sum = (a: Int, b: Int) => a + b
val fOption: Option[Int => Int] = Functor[Option].map(Some(3), sum.curried)

Applicative[Option].ap(Some(4), fOption)
// res4: Option[Int] = Some(7)

Some(4) <*> fOption

Extensions

trait Applicative[F[_]] extends Apply[F] with  Functor[F] { 
  def pure[A](a: A): F[A]

  def map2[A, B, C](
    a: F[A], 
    b: F[B], 
    c: (A, B) => C): F[C] = 
    ap(b, Fucntor[A].map(a, c.curried))
}

Monad

Monad

It’s really not that scary

Monad

trait Monad[F[_]] extends Applicative[F] {
  def flatMap[A, B](a: F[A])(f: A => F[B]): F[B]
}

Why?

def getUser(id: String): Option[User]
def getAddress(user: User): Option[Address]

def getAddressForId(id: Sting) = 
  getUser(id).flatMap { user => 
    getAddress(user)
  }

This gets ugly really fast.

for-comprehension

  • Syntactic sugar built into the Scala compiler.
  • Similar construct (do-notation) exists in Haskell
def getPOBoxForId(id: String) = for { 
  user    <- getUser(id)
  address <- getAddress(user)
  pobox   <- getPOBox(address)
} yield address

Laws

Left Identity

pure(a).flatMap(f) == f(a)

Right Identity

m.flatMap(pure) == m

Associativity

flatMap(flatMap(m)(f))(g) == flatMap(m)(x => flatMap(f(x))(g))
(m >>= f) >>= g == m >>= (x => f(x) >>= g)

Examples

implicit val optionMonad = new Monad[Option] { 
  def flatMap[A, B](a: Option[A])(f: A => Option[B]) = a match { 
    case None => None
    case Some(x) => f(x)
  }
}

Monads are your friends

Popular Monads

  • Option
  • Either
  • List
  • But wait! There’s more!

Reader

Reader[I, A]

I => A

Writer

Writer[A]

A => Unit

State

State[S, A]

S => (A, S)

IO

IO[A]

for { 
  name <- IO { readLine("What is your name?") }
  _    <- IO { print(s"Hello, $name") }
} yield ()

Stream

(specifically, fs2.Stream)

Stream[F[_], A]

https://github.com/functional-streams-for-scala/fs2

Free

More on this later…

Additional Resources

?

Thank You!