Accueil Le blog ebiznext
3. HOF in FP

This note is the last in a series of posts dedicated to functional programming.  It follows that previous post

Higher Order Functions are definitely what will allow us to write less code throughs techniques that OOP cannot provide us with.

Let’s say that our boss ask us to add the following functions to the list trait: sum & product.

Let’s do it the OO way

case object Nil extends List[Nothing]
case class Cons[+A](car: A, cdr: List[A]) extends List[A]
sealed trait List[+A]
object List {
  def sum(list: List[Double]): Double = list match {
    case Nil => 0
    case Cons(car, cdr) => car + sum(cdr)
  }
  def product(list: List[Double]): Double = list match {
    case Nil => 1
    case Cons(car, cdr) => car * product(cdr)
  }
}

We can notice that the algorithm is exactly the same for both functions, only the initial (0 for sum and 1 for product) value and the function applied (+ in the case of sum and * in the case of product) are different. Both, sum and product are functions that can be defined by the same algorithm parameterized by the initial value and the function applied to each element.
We thus rewrite our code as follows:

case object Nil extends List[Nothing]
case class Cons[+A](car: A, cdr: List[A]) extends List[A]
sealed trait List[+A]
object List {
  def foldRight(list: List[Double], initial: Double)(f : (Double, Double) => Double) : Double = {
    list match {
      case Nil => initial
      case Cons(car, cdr) => f(car, foldRight(cdr, initial)(f))
    }
  }  
  def sum(list: List[Double]) = foldRight(list, 0.0) { (a, b) => a + b }
  def product(list: List[Double]) = foldRight(list, 1.0) { (a, b) => a * b }  
}

HOF in FP is all about combining algorithms: A generic one and a specific one. The specific one being executed as part of the more generic one.

P.S. Notice that we could hare written (a, b) => a + b above using the following syntax _ + _