Compose, Curry and Recursion
Function Composition #
A set of functions that are combined together into a single function using function composition. Its typically like function composition in Math where
(f ∘ g)(x) = f[g(x)]
We know functions are centered topic in this paradigm, and codes are just a series of functions that applies transformation over the input that is piped from a function to a function, think of it as a train compartments where an input gets from one compartment to another.
Let’s say we have a function that increments the given input and another function that check if the input is odd.
type Increment = (a: number) => number
const increment = x => x + 1
type IsOdd = (a: number) => boolean
const isOdd = x => x % 2 ? false : true
So we would like to pass the input to increment function and pass the outcome to the isOdd function.
Coding it with imperative style by defining each steps.
const x = 5 // input
const incrementOutput = increment(x)
const isOddOutput = isOdd(increment)
console.log(isOddOutput)
So we see we tell the program how to do rather than what to do. Let’s make this code functionally by combining these two functions.
type Increment = (a: number) => number
const increment = x => x + 1
type IsOdd = (a: number) => boolean
const isOdd = x => x % 2 ? false : true
// We create another function that combine these two functions.
// Given that we infer the input type of function A
// and the result type of function B
type IncThenIsOdd = (x: number) => boolean
const incThenIsOdd: IncThenIsOdd = x => isOdd(increment(x))
console.log(incThenIsOdd(5))
This is a solution but hey, the functions are hardcoded inside the body. Can’t we make a function that compose two given functions as arguments and return a composed function of it? Let’s try it.
type Compose = (
f: (x: number) => boolean,
g: (x: number) => number
) => (x: number) => boolean
const compose: Compose = (f, g) => x => f(g(x))
type IncThenIsOdd = (x: number) => boolean
const incThenIsOdd: IncThenIsOdd = compose(isOdd, increment)
console.log(incThenIsOdd(5))
What we did is defining a function signature that takes two function, one function receives a number and returns a Boolean and the receiving a number and returns a number. Notice the order here matter, the second function result is used as the input of the first function. We can’t do the opposite cause of the strict type.
The above code is fair enough but what if we want to compose two other functions that have different types say toString function where it takes a number and cast it to string. We need to redefine the type of the compose function again.
Thankfully, using the power of TypeScript we can generalize and abstract the compose function with the use of generics.
Let’s leverage generics to generalize our compose function
type Compose = <A,B,C>(
f: (x: B) => C,
g: (x: A) => B
) => (x: A) => C
const compose: Compose = (f, g) => x => f(g(x))
type Increment = (a: number) => number
const increment = x => x + 1
type IsOdd = (a: number) => boolean
const isOdd = x => x % 2 ? false : true
type ToStr = (a: number) => string
const toStr = x => `${x}`
// Compose increment and isOdd
type IncThenIsOdd = (x: number) => boolean
const incThenIsOdd: IncThenIsOdd = compose(isOdd, increment)
// Compose increment and toStr
type IncThenToStr = (x: number) => string
const incThenToStr: IncThenToStr = compose(toStr, increment)
Cool, we generalize compose function to accept any type but it must adhere with the rule that function f must receives same input type of the output type of the function g which is B.
We can’t compose isOdd and toStr because there is no common type in between those function.
This can be solved later.
Function Curry #
Function currying is about transforming a function of N-aray to unary function that takes only one input. Why this matter? Reusability
In functional programming, functions only receives one input and there are called Unary Function.
Example of a multiply function and converting it to unary function
// Two input passed to the function
const multiply = (x, y) => x * y
// We curry the function by treating
// the function as value
const multiplyCurried = x => y => multiply(x, y)
// 2 x 3 = 6
console.log('2 x 3 =', multiply(2, 3))
console.log('2 x 3 =', multiplyCurried(2)(3))
In the curried function, when calling it with the first argument, it returns a function that accepts another single input.
We can use the curried function to build other functions to achieve reusability and avoid writing excessive code.
// A log function
const log = (date, level, msg) => `[${date.getTime()}] [${level}] ${msg}`
console.log(log(new Date(), 'INFO', 'Server started on port 8080'))
// We can create function from existing function
const logCurried = date => level => msg => log(date, level, msg)
const logNow = logCurried(new Date())
console.log(logNow('INFO')('Server started on port 8080'))
// We even can create different type of logger
// from base logger
const logInfo = logCurried(new Date())('INFO')
const logDebug = logCurried(new Date())('DEBUG')
console.log(logInfo('Server started on port 8080'))
console.log(logDebug('API request received: Endpoint=/api/data, Method=POST'))
All looks fine but something missing, ABSTRACTION. We need to create a generalized function that takes a function and translate it to curried function.
type Curry = <A, B, C>(
f: (a: A, b: B) => C
) => (a: A) => (b: B) => C
const curry = f => a => b => f(a, b)
const multiply = (x, y) => x * y
const multiplyCurried = curry(multiply)
console.log(`2 x 3 =`, multiply(2, 3))
console.log(`2 x 3 =`, multiplyCurried(2)(3))
Function Recursion #
In functional programming, loops aren’t presented hence we need to model a repetitive tasks without loops, recursion in the rescue.
The function call it self over and over until it hits the edge case.
type Sum = (x: number[]) => number;
const sum: Sum = (x: number[]) => {
// Here the edge case
// where the array is
// empty, return 0
if (x.length === 0) return 0;
// We use spread operator
const [head, ...rest] = x;
// Now here the function
// calls itself over and
// over until it hits the
// edge case E.g.
return head + sum(rest);
}
console.log(sum([1,2,3,4]));
Fair enough, but we can tweak a little bit to make it more functional style, because used to define variables inside the function.
type Sum = (num: number[]) => number
const sum: Sum = num => num.length === 0 ? 0 : num[0] + sum(num.slice(1))
console.log(sum([1,2,3,4]));