Scala 3 - Tail Recursion & Higher-Order Functions 1

스칼라 튜토리얼, scala의 tail recursion을 알아봅시다

---

Recursion needs care

Let's look at typical summation fuction.

def sum(n: Int) : Int = 
  if (n <= 0) 0 else (n + sum(n-1))

In this recursion, child function has to return to its parent function because there is remaining computation needs to be done.

---

Tail Recursion

import scala.annotation.tailrec

def sum(n: Int): Int = {
  @tailrec def sumItr(res: Int, m: Int): Int =
    if (m <= 0) res else sumItr(m + res, m-1)
  sumItr(0, n)
}

In tail recursion case, there is no computation remaining in the parent function, therefore saves stack frame(actually, it needs single stack frame).

---

Higher-Order Functions

Functions as Values

Functions are normal values of function types.

They can be copied, passed and returned.

Functions that take functions as arguments or return functions are called higher-order functions.

Higher-order functions increase code reusability.

Examples : Make it more reusable!

def sumLinear(n: Int): Int = 
  if (n <= 0) 0 else n + sumLinear(n-1)
def sumSquare(n: Int): Int = 
  if (n <= 0) 0 else n*n + sumSquare(n-1)
def sumCubes(n: Int): Int = 
  if (n <= 0) 0 else n*n*n + sumCubes(n-1)

• Solution 1 :

def sum(f: Int => Int, n: Int): Int =
  if (n <= 0) 0 else f(n) + sum(f, n-1)

def linear(n: Int) = n
def square(n: Int) = n * n
def cube(n: Int) = n * n * n

def sumLinear(n: Int) = sum(linear, n)
def sumSquare(n: Int) = sum(square, n)
def sumCubes(n: Int) = sum(cube, n)

---

Anonymous Functions

• Syntax

(x1 : T1, ... xn : Tn) => e
or
(x1, x2, ... xn) => e

By using anonymous functions, we can make 'Solution 1' above more simple.

def sumLinear(n: Int) = sum((x : Int) => x, n)
def sumSquare(n: Int) = sum((x:Int)=>x*x, n)
def sumCubes(n: Int) = sum((x:Int)=>x*x*x, n)

// or

def sumLinear(n: Int) = sum((x)=>x, n)
def sumSquare(n: Int) = sum((x)=>x*x, n)
def sumCubes(n: Int) = sum((x)=>x*x*x, n)

---

Excercise

def sum(f: Int => Int, a: Int, b: Int): Int =
  if (a <= b) f(a) + sum(f, a+1, b) else 0

def product(f: Int=>Int, a: Int, b: Int): Int = 
  if (a <= b) f(a) * product(f, a+1, b) else 1  

DRY(Do not Repeat Yourself) using a higher-order function, called "mapReduce"

Mapreduce accepts a list of arbitrary values and returns one single value that combines all the values returned by map.

• Solution 2 :

def mapReduce(combine: (Int, Int) => Int, inival: Int, f: Int => Int, a: Int, b: Int): Int = {
  if (a <= b) combine(f(a), mapReduce(combine, inival, f, a+1 b))
  else inival
}

def sum(f: Int => Int, a: Int, b: Int): Int = 
  mapReduce((x, y) => x+y, 0, f, a, b)

def product(f: Int => Int, a: Int, b: Int): Int =
  mapReduce((x, y) => x*y, 1, f, a, b)

print(sum((x) => x*x*x, 1, 100))  // print sumCubes from 1 to 100
print(product((x) => x*x, 1, 5))  // print productSquare from 1 to 5

---

Closures for functional values

Let's see how it works!

val t = 0
val f = {
  val t = 10
  def g(x: Int) : Int = x + t
  g _ }
f(20)

In the above code, you will notice there is underbar( _ ) next to 'g'.

What does it mean and how it works?

• Explanation :

함수 자체를 값으로 쓰기 위해서는 close가 되어야 하고, 이 close를 해주는 패키지를 closure이라고 한다.

이는 함수가 정의된 환경에서, 함수를 return하거나, argument로 사용하기 위해 '값'을 정의해 주기 위해 사용하는 기능이다.

즉, 위의 5번째 라인에서 g(10)이런 식으로 쓰는 것은 가능하겠지만, g만 쓰면 함수 호출만 의미하는 것이므로, closed가 되어 있지 않기 때문에 underbar( _ )를 붙여 주어야 한다.

• More details about closure(from wikipedia) :

In programming languages, a closure (also lexical closure or function closure) is a technique for implementing lexically scoped name binding in a language with first-class functions.

Operationally, a closure is a record storing a function together with an environment. The environment is a mapping associating each free variable of the function (variables that are used locally, but defined in an enclosing scope) with the value or reference to which the name was bound when the closure was created.

A closure—unlike a plain function—allows the function to access those captured variables through the closure's copies of their values or references, even when the function is invoked outside their scope.

• Example :

function add(x)
   function addX(y)
       return y + x
   return addX

variable add1 = add(1)
variable add5 = add(5)

assert add1(3) = 4
assert add5(3) = 8

Note that, as add returns a value of function type, the variables add1 and add5 are also of function type.

Wikipedia Link