Map

def map[A, B](f: A => B)(opt: Option[A]): Option[B] = opt match {
  case Some(x) => Some(f(x))
  case None => None
}

def map2[A,B](f: A => B)(opt: Option[A]): Option[B] = {
  opt flatMap (a => Some(f(a)))
}

getOrElse

def getOrElse[A, B >: A](default: => B)(opt: Option[A]): B = opt match {
  case Some(x) => x
  case None => default
}

flatMap

def flatMap[A, B](f: A => Option[B])(opt: Option[A]): Option[B] = opt match {
  case Some(x) => f(x)
  case None => None
}

def flatMap2[A, B](f: A => Option[B])(opt: Option[A]): Option[B] = {
  opt map f getOrElse None
}

Filter

  def filter[A](f: A => Boolean)(opt: Option[A]): Option[A] = opt match {
    case Some(x) => if (f(x)) Some(x) else None
    case None => None
  }

  def filter2[A](f: A => Boolean)(opt: Option[A]): Option[A] = {
    opt flatMap (a => if (f(a)) Some(a) else None)
  }

It’s fairly interesting to notice how my first attempt to write this was flawed:

def filter_wrong[A](f: A => Boolean)(opt: Option[A]): Option[A] = {
  opt map (a => if (f(a)) a else None)
}

This is wrong because I’m passing to map a function that returns two different types: A in one case and None in the other, so that the return type is Option[Any] rather than Option[B].

Fold: the thing is to keep in mind is that folding an Option is the equivalent of chaining map and getOrElse:

Some(1) map identity getOrElse 10
Some(1).fold(10)(identity)
None.fold(10)(identity)

the implementation is therefore straightforward:

def foldOption[A, B](z: B)(op: A => B)(opt: Option[A]): B = opt match {
  case Some(a) => op(a)
  case None => z
}

mapCombine is just a way to showcase how for comprehensions are just syntactic sugar for chaining maps and flatMaps:

def mapCombine[A,B,C](a: Option[A], b: Option[B])(f: (A,B) => C): Option[C] = {
  for {
    aa <- a
    bb <- b
  } yield f(aa,bb)
}

def mapCombine2[A,B,C](a: Option[A], b: Option[B])(f: (A,B) => C): Option[C] = {
  a flatMap { aa =>
    b map { bb => f(aa,bb) }
  }
}

Last but not least, something more interesting, sequence and traverse.

def sequence[A](as: List[Option[A]]): Option[List[A]] = {
  as.foldRight[Option[List[A]]](Some(Nil)){ (maybeA, maybeAs) =>
    maybeA match {
      case Some(a) => maybeAs map (as => a :: as)
      case None => None
    }
  }
}

How this works: it starts with an empty list of as, our accumulator maybeAs; then it starts looping through List[Option[A]].
If we have an a, we add it to the accumulator;
If we don’t have an a, the accumulator becomes None, so that for all the next maybeA it will be None and the line maybeAs map ... will actually be None map ..., thus exhausting the list and eventually returning None.

Traverse can be easily implemented using sequence:

def traverse[A,B](as: List[A])(f: A => Option[B]): Option[List[B]] = {
  sequence(as map f) // where (as map f) is a List[Option[B]]
}

Or less easily implemented from scratch:

def traverse2[A,B](as: List[A])(f: A => Option[B]): Option[List[B]] = {
  as.foldRight[Option[List[B]]](Some(Nil)) { (a, maybeAcc) =>
    f(a) match {
      case Some(v) => maybeAcc map (acc => v :: acc)
      case None => None
    }
  }
}

This is slightly inefficient because we’re computing f(a) for every a in as, even if the accumulator is set to None. This leads to an obvious improvement:

def traverse3[A,B](as: List[A])(f: A => Option[B]): Option[List[B]] = {
  as.foldRight[Option[List[B]]](Some(Nil)) { (a, maybeAcc) =>
    maybeAcc match {
      case Some(acc) => f(a) map (aa => aa :: acc)
      case None => None
    }
  }
}

Finally, we can reimplement sequence using traverse:

def seqViaTraverse[A](as: List[Option[A]]): Option[List[A]] = {
  traverse3(as)(identity)
}