Questions and Completion

There is nothing to hand in for the worksheet, but you should definitely work through it in order to prepare for the quiz and homework.

If you have questions as you go through this worksheet, please feel free to post them on the discussion forum.

Option Type

Maximum of a List

Write a recursive function that returns the maximum of a list of integers.

Instead of throwing an exception when the list is empty, return an Option type. That is, your function should have the following form.

  def maximum (xs:List[Int]) : Option[Int] = {
    ...
  }

Solution: Maximum of a List

Find Element

Write a higher-order function that finds the first element in a list that satisfies a given predicate (function taking an element of the list and returning a Boolean value).

Instead of throwing an exception when no such element is found, return an Option type. That is, your function should have the following form.

  def find [X] (xs:List[X], p:X=>Boolean) : Option[X] = {
    ...
  }

Solution: Find Element

Handle an Option - Pattern Matching

Consider the following Scala function. It searches for the first String in a list of String references that is strictly longer than s and that contains s as a substring.

  def oneFind (xs:List[String], s:String) : Option[String] = {
    xs.find ((x:String) => (x.length > s.length) && x.contains (s))
  }

For example:

scala> oneFind (List ("the", "rain", "in", "spain"), "i")
res1: Option[String] = Some(rain)

scala> oneFind (List ("the", "rain", "in", "spain"), "in")
res2: Option[String] = Some(rain)

scala> oneFind (List ("the", "rain", "in", "spain"), "ain")
res3: Option[String] = Some(rain)

scala> oneFind (List ("the", "rain", "in", "spain"), "pain")
res16: Option[String] = Some(spain)

scala> oneFind (List ("the", "rain", "in", "spain"), "rain")
res4: Option[String] = None

Now write a function twoFind that calls oneFind and then uses the result (if there is one) in a second call to oneFind.

Use pattern-matching to do case analysis on the result of the first call to oneFind. Your definition of twoFind should have the following form.

  def twoFind (xs:List[String], s:String) : Option[String] = {
    ...
  }

Note that twoFind must not have return type Option[Option[String]]!

For example:

twoFind (List ("the", "rain", "in", "spain"), "i")
res1: Option[String] = None

scala> twoFind (List ("the", "rain", "in", "spain"), "in")
res2: Option[String] = None

scala> twoFind (List ("the", "rain", "in", "spain"), "n")
res3: Option[String] = None

scala> twoFind (List ("the", "rain", "in", "spain", "trained", "after", "a", "sprain"), "in")
res4: Option[String] = Some(trained)

scala> twoFind (List ("the", "rain", "in", "spain", "trained", "after", "a", "sprain"), "i")
res5: Option[String] = Some(trained)

scala> twoFind (List ("the", "rain", "in", "spain", "trained", "after", "a", "sprain"), "n")
res6: Option[String] = Some(trained)

scala> twoFind (List ("the", "rain", "in", "spain", "trained", "after", "a", "sprain"), "ain")
res7: Option[String] = Some(trained)

scala> twoFind (List ("the", "rain", "in", "spain", "trained", "after", "a", "sprain"), "pain")
res8: Option[String] = None

Solution: Handle an Option - Pattern Matching

Handle an Option - flatMap

Rewrite twoFind from the previous question to use flatMap for the Option type instead of explicit pattern-matching.

Note: if e has type Option[A] and you write e.flatMap (f), then it will have type Option[B] whenever f has type A=>Option[B]. You may find it helpful to look at the description for the Option type in the Scala API documentation.

Variations of flatMap are idiomatic in many languages that use Option types.

Solution: Handle an Option - flatMap

Solutions

Solution: Maximum of a List

  def maximum (xs:List[Int]) : Option[Int] = {
    xs match {
      case Nil   => None
      case y::ys => 
        maximum (ys) match {
          case None => Some (y)
          case Some (z) => Some (y max z)
        }
    }
  }

Suppose we start with maximum (List(11,31,21)). Computation goes as follows:

 maximum (List(11,31,21))
=> maximum (List(31,21)) match [with y=11] { ... }
=> (maximum (List(21)) match [with y=31] {...}) match [with y=11] { ... }
=> ((maximum (List()) match [with y=21] {...}) match [with y=31] {...}) match [with y=11] { ... }
=> ((None match [with y=21] {...}) match [with y=31] {...}) match [with y=11] { ... }
=> (Some(21) match [with y=31] {...}) match [with y=11] { ... }
=> Some(31 max 21) match [with y=11] { ... }
=> Some(31) match [with y=11] { ... }
=> Some(11 max 31)
=> Some(31)

It’s actually easier to understand if you starting at Nil by running on progressively longer lists:

 maximum(List())
=> None

maximum(List(21))
=> maximum(List()) match {...}
=> None match {...}
=> Some(21)

maximum(List(31,21))
=> maximum(List(21)) match {...}
=> Some(21) match {...}
=> Some(31 max 21)
=> Some(31)

maximum(List(11,31,21))
=> maximum(List(31,21)) match {...}
=> Some(31) match {...}
=> Some(11 max 31)
=> Some(31)

Recall that match is simply short-hand for if-else and is evaluated left to right. So the definition above is equivalent to:

def maximum (xs:List[Int]) : Option[Int] = {
  if (xs == Nil) {            //case Nil
    None
  } else {                    // case y::ys
    val y = xs.head
    val ys = xs.tail
    val zoption = maximum (ys)
    if (zoption == None) {    // case None
      Some (y)
    } else {                  // case Some(z)
      val z = zoption.get
      Some (y max z)
    }
  }
}

Solution: Find Element

  def find [X] (xs:List[X], p:X=>Boolean) : Option[X] = {
    xs match {
      case Nil            => None
      case y::ys if p (y) => Some (y)
      case _::ys          => find (ys, p)
    }
  }

This one is easier since tail recursive:

def p = (x:Int) => (x==5)

find(List(11,5,21), p)
=> find(List(5,21), p)
=> Some(5)

find(List(11,21), p)
=> find(List(21), p)
=> None

Solution: Handle an Option - Pattern Matching

  def oneFind (xs:List[String], s:String) : Option[String] = {
    xs.find ((x:String) => (x.length > s.length) && x.contains (s))
  }

  def twoFind (xs:List[String], s:String) : Option[String] = {
    oneFind (xs, s) match {
      case None     => None
      case Some (t) => oneFind (xs, t)
    }
  }

Solution: Handle an Option - flatMap

  def oneFind (xs:List[String], s:String) : Option[String] = {
    xs.find ((x:String) => (x.length > s.length) && x.contains (s))
  }

  def twoFind (xs:List[String], s:String) : Option[String] = {
    oneFind (xs, s).flatMap ((t:String) => oneFind (xs, t))
  }