# Implementing functional combinators for Scala Options

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) }