# 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

# 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