Option Types and Evaluation Strategy

This walkthrough connects two lecture threads from week 6: (1) replacing null-style programming with Option, and (2) understanding call-by-value versus call-by-name behavior.

1) Baseline: find with null

The first version returns null when no element satisfies the predicate.

def findNull[X](xs: List[X], p: X=>Boolean) : X = xs match
  case Nil => null
  case x :: rest =>
    if p(x) then x
    else findNull(rest, p)
end findNull

This style works, but every use site must remember explicit null checks. That extra burden appears immediately in fallback logic.

2) Fallback search with manual null checks

We search for an element > 5; if missing, we try > 3.

val l = List(1,2,3,4,5)
val r1 = findNull(l, _ > 5)
val r =
  if r1 != null then r1
  else findNull(l, _ > 3)

if r != null then println("Found")
else println("Not found")

The control flow is more error-prone because absence is represented by a raw value (null). Next we encode absence explicitly in the type.

3) Refactor find to return Option

Now absence is None and a successful result is Some(x).

def find[X](xs: List[X], p: X=>Boolean) : Option[X] = xs match
  case Nil => None
  case x :: rest =>
    if p(x) then Some(x)
    else find(rest, p)
end find

This makes the API safer: callers must handle both cases by pattern matching or combinators.

4) Compose searches with orElse

Option allows direct fallback composition without null checks.

find(l, _ > 5) orElse find(l, _ > 3) match
  case None => println("Not found")
  case Some(x) => println(s"Found $x")

The same logic is now concise and explicit about success/failure cases. The following helper shows what orElse means operationally.

5) Explain orElse behavior explicitly

def myOrElse[X](o1: Option[X], o2: Option[X]) =
  o1 match
    case None => o2
    case Some(x) => Some(x)

This reinforces the semantics: keep the first success, otherwise use the fallback. The lecture then transitions from safety in values to safety in evaluation behavior.

6) Call-by-value versus call-by-name

With call-by-value, the argument is evaluated once before entering the function.

def f(x: Double) : Double =
  val x1 = x
  val x2 = x
  x1 - x2
end f

f(Math.random())

With call-by-name (=>), each use can re-evaluate the argument expression.

def g(x: => Double) : Double =
  val x1 = x
  val x2 = x
  x1 - x2
end g

g(Math.random())

Because Math.random() may run twice in g, the result is not guaranteed to be 0. This sets up later abstractions (thunks and custom control constructs) where evaluation timing is intentional.