foldAndMapAndFlatMap.scala

// Taken from Essential Scala by Noel Welsh and Dave Gurnell

// fold: structural recursion
sealed trait LinkedList[A] {
  def fold[B](end: B)(pair: (A, B) => B): B =
  this match {
    case End() => end
    case Pair(hd, tl) => pair(hd, tl.fold(end, pair))
  }
}
final case class Pair[A](head: A, tail: LinkedList[A]) extends LinkedList[A]
final case class End[A]() extends LinkedList[A]

// We have a type F[A] and a func on A => B, and we want a result F[B]
// _map the happy to a new type_
// Examples:
// - List[ID] and a func of ID => User, and we want to get a List[User]
sealed trait LinkedList[A] {
  def map[B](fn: A => B): LinkedList[B] =
    this match {
      case Pair(hd, tl) => Pair(fn(hd), tl.map(fn))
      case End() => End[B]()
  }
}
final case class Pair[A](head: A, tail: LinkedList[A]) extends LinkedList[A]
final case class End[A]() extends LinkedList[A]

// We have a type F[A] and a func on A => F[B], and we want a result F[B]
// _map the internal happy to a new type_
// Examples:
// - List[User]and a func of User => List[Order], and we want List[Order]
// - Maybe[User] and a func of User => Maybe[Order], and we want Maybe[Order]
// - Sum[String, Order] and a func of Order => Sum[String, Id], and we want Sum[String, Id]
sealed trait Maybe[A] {
  def flatMap[B](fn: A => Maybe[B]): Maybe[B] =
    this match {
      case Full(v) => fn(v)
      case Empty() => Empty[B]()
  }
}
final case class Full[A](value: A) extends Maybe[A]
final case class Empty[A]() extends Maybe[A]

// A type like F[A] with a `map` method is called a _functor_.
// If a _functor_ also has a `flatMap` method it is called a _monad_.