Higher Order Functions

Higher Order Functions (HOF) are the heart of the FP. They’re defined as a functions which takes as an argument and/or return other function(s). This is quite simple and powerful concept.

Let’s create class SimpleCalculator.

class SimpleCalculator {
  def p1, p2
  def add = { p1+p2 }
  def sub = { p1-p2 }
}

Imagine you want to add another calculator methods like multiply or divide etc. In OOP you need to change class definition or inherite then use new methods. In Groovy you can even inject new methods.

  SimpleCalculator.metaClass.mul = { p1*p2 }
  def sc = new SimpleCalculator(p1:3,p2:4)
  println sc.mul()
  // result: 12

When you want add more and more methods you need to change class definition more and more. If class is highly coupled maintaining of the code could be complicated. HOF is the answer here. Instead of producing methods, extract common operation pattern to HOF – here we make calculate. This function will accept another function (closure) which do what is exactly needed in your code. It’s like injecting required functionality in place where it’s actually needed.

class SimpleCalculatorF extends SimpleCalculator {
  // take closure and run it on p1 and p2 attributes
  def calculate = { closure -> closure(p1,p2) }
}

def sc2 = new SimpleCalculatorF(p1:8,p2:11)

println sc2.calculate { a,b -> (a+b)/2.0 } // average
// result: 9.5
println sc2.calculate { a,b -> b % a } // mod
// result: 3

Map, Fold, Filter

Map, Fold and Filter are three Higher Order Functions which are key to effectively operate on data (collections). These three can make almost everything with collection: iterate, select, transform and analyse or calculate. How they work:
Map – take each element and apply closure on it, as a result return transformed collection. In Groovy function has name collect. Few examples:

// square collection
println ([1,2,3,4].collect { it * it })
// result: [1,4,9,16]

// which is even or odd?
println ([1,2,3,4].collect { it % 2 == 0 ? "even" : "odd"})
// result: [odd, even, odd, even]

// map operation
println (["a":1, "b":3, "c":2].collect { key, val -> (1..val).collect { key } })
// result: [[a], [b, b, b], [c, c]]

Fold or Reduce – iterate through collection and apply two parameter closure on every item and temporary value which is the result from previous closure call or value you passed to Fold function during the first iteration step. In Groovy function has name inject.

// sum
println ( [1,2,3,4].inject(0) { temp, val -> temp + val} )
// result: 10

// temp = 0 (initial value)
// temp + each val
//    0 + 1 = 1
//    1 + 2 = 3
//    3 + 3 = 6
//    6 + 4 = 10
// result: 10

// number of odds and evens
println ( [3,2,5,4,6,6,8,9,11].inject([0,0]) { temp, val -> 
  def (even, odd) = temp
  val % 2 == 0 ? [even+1,odd] : [even,odd+1]
})
// result: [5, 4]

Filter – In Groovy findAll. Just select only these elements which satisfy given condition.

// take even values
println ( [3,2,4,3,5].findAll { it % 2 == 0 } )
// result [2, 4]

Last thing to mention:

Join Anti-For campaign: less For/While loops more Map/Filter/Fold

Advertisements

Iterations

There are many startegies how to iterate. I will show few of them using everlasting example: factorial (sorry).

Imperative way

def factorial_imp = { n ->
  int acc = 1;
  for(int i=n;i>0;i--) acc *= i
  return acc
}

println factorial_imp(5)
// result: 120

Here I use for-loop (while could be good as well) and local variables which are used to manage internal state. It’s not FP way. Try to avoid them.

Recursion

def factorial_rec
factorial_rec = { n ->
  if(n == 0) 1
  else n * factorial_rec(n-1)
}

println factorial_rec(5)
// result: 120

Better. No variables at all, no for-loop. But this version of recursion uses stack havily. See call stack below:

// factorial_rec(5)
// 5 * factorial_rec(4)
// 5 * 4 * factorial_rec(3))
// 5 * 4 * 3 * factorial_rec(2)
// 5 * 4 * 3 * 2 * factorial_rec(1)
// 5 * 4 * 3 * 2 * 1 * factorial_rec(0)
// 5 * 4 * 3 * 2 * 1 * 1
// 5 * 4 * 3 * 2 * 1
// 5 * 4 * 3 * 2
// 5 * 4 * 6
// 5 * 24
// 120

The reason is that last operation in function is multiply. Function needs to evaluate all recursive calls to finally multiply temporal results. Let’s change it.

Tail recursion

def factorial_tailrec = { n ->
  def loop
  loop = { acc, num ->
    if(num == 0) acc
    else loop(acc * num, num - 1)
  }
	
  loop(1,n)
}

println factorial_tailrec(5)
// result: 120

Here I moved step calculation to the argument and recursive call is the last operation we do in the function. Therefore code is executed linearly.

// factorial_tailrec(5)
// loop(1,5)
// loop(5,4)
// loop(20,3)
// loop(60,2)
// loop(120,1)
// loop(120,0)
// 120

So this is how it should be done. But…

Erik Meijer: Recursion is the GOTO of functional programming

So…

Inject

def factorial_fold = { n ->
  if(n==0) 1
  else (1..n).inject(1) {result, i -> result * i }
}

println factorial_fold(5)
// result: 120

Here I use higher order function (see next post) called ‘inject’ (fold or reduce in other languages). I think this is most elegant way for iterations.

Functional Programming in Groovy

Hi. In few following posts I’ll try to show few Functional Programming concepts and how to use them in Groovy programming language.

Concepts are:

  1. Iterations
  2. Higher Order Functions (HOF)
  3. Memoization
  4. Currying
  5. Combinators
  6. Monads

All of above topics were subject of internal company’s Functional Programming workshop. Just wanted to share it.

What is Functional Programming (FP) you can read and learn here:˜