Another Functional Programming Challenge

[[)roi(]]

Continuing from the last thread on how to solve problems with a more functional style
This thread will be quite a bit different, because it's going to focus on a particular FP pattern (algebra).

To start:
Let's start with a simple challenge to create a function that can generate output from the composition of 2 arrays:

Array of single arity functions (and/or closures) from type Integer to type Integer:

[{x => 2 * x - 1}, {x => 2 * x}] // odd and even numbers

Note:

• Functions can be declared separately and then just referenced in the array.

Array of Integers:

[1, 2, 3, 4, 5]

Output:

[1, 3, 5, 7, 9, 2, 4, 6, 8, 10]

Bonus points:
If your function can supports a generic transformation from any type to any type.

Extra bonus points:
If you can correctly identify this pattern.


Part 2:
Demonstrate how this pattern can be used to streamline processes like data validation, parsing, etc.
Bonus Points:
Demonstrate how using this pattern can be tweaked to capture all the validation errors as opposed to breaking out on the first error encountered.
Extra Bonus Points:
Demonstrate how this pattern can be used to multithread asynchronous processes.

Pattern validation rules (optional for this challenge)
As with most mathematically originated algebras; here are the rules that affirm correct behaviour.



Note:
In this example we are applying a functional pattern to an Array, however this pattern works equally well with any container object, I.e. an object that wraps some data, for example:

• Optional
• Result
• Either
• LinkedList
• Trie
• Tuples
• Future
• Promise
• Etc.

Languages:
Some languages are more difficult than others when extending existing container types, for example: Java

• which sadly still doesn't provide a simple way to add extra methods and/or operators without a lot of inheritance boilerplate.
• or alternatively the added complexity of something like Java 8's Stream class e.g. to lift an existing container into a new container with the added methods using type erasure.

Note:

• This pattern isn't well formulated with standalone / static functions due bracketing; it preferably needs something like method extension, operator overloading and / or infix functions.
• Languages like Python, Kotlin, Scala, Swift, Ruby, ... are far easier to extend.

Submissions
Go ahead and submit your solutions / answers for any or all of the parts you like. Ask away for any further clarity.

Good luck.

After a week I'll again publish a detailed write up on this, to both explain the pattern, and to show how it works for not only Arrays but also the Optional, Result and Future types. Considering the full scope of this challenge I will only be preparing solutions to this in a maximum of 2 languages (let me know if you have a preference).

 

[[)roi(]]

Still no takers for the challenge?

In the meantime
Let me cover a supporting pattern that accompanies the use of these algebras (patterns);

CURRYING
Functional programming with its strong ties with mathematics; defines functions in the mathematical sense:

1. Every point in the domain (set of input) must have a resulting value in the codomain (set of outputs).
2. No value in the domain can result in two or more matching results in the codomain (must be 1 to 1).
3. However two domain values can match up to the same codomain value. i.e. 1 to 1 is left associative.

To take advantage of mathematic algebras and their axioms we need to ensure that our building blocks: functions similarly conform to mathematical rules for functions.

A perfect example of a non mathematical function
Which is also termed a non pure function; is one that either mutates state or whose computation is affected by state, for example:

• Random number generation

What about functions that require multiple input parameters?
Many object initialisers usually require more than one parameter, for example:

struct User {
  let id: Int
  let name: String
  let surname: String
  let email: String
}

Swift compiler generates a default initialiser for the above User type that looks like this

extension User {
 init(id: Int, name: String, surname: String, email: String) {
    self.id = id
    self.name = name
    self.surname = surname
    self.email = email
  }
}

Which quite clearly is a function that requires 4 parameters as input i.e. not the 1 parameter that mathematical algebras typically use? So how can we make this conform?

Option 1: Tuples?
In mathematics, a tuple is a finite ordered sequence of elements. Each of these elements can be of a different type, for example: Integer followed by a String, ....

This is more typically represented a sequence of values wrapped in parenthesis, for example:

(1, "Jack", "Sprat", "[email protected]")

Let's define a function that takes in 1 tuple with all the parameters.

let createUser = { (id, name, surname, email) in User(id: id, name: name, surname: surname, email: email) }
let jack = createUser((1, "Jack", "Sprat", "[email protected]"))

The entire sequence of tuple values is treated as a single input set with a finite number of elements; but always exactly matches the requirement of the internal function definition. Essentially this is just a different way to think of and represent multiple parameters; it certainly does not change the nature of the input -- all values are still required all at once.

Option 2: Partial Application?
In computer science, partial application refers to the process of fixing a number of arguments to a function, and there by producing another function of smaller arity. This is in the functional sense is quite analogous to dependency injection.

Example: Let's say we want to assign the same id and surname to more than one user; we can define a new function where those two values are affixed and a new function is returned that only requires the name and the email.

let createFamilyMember(id: Int, surname: String) -> (String, String) -> User {
  return { (name, email) in User(id: id, name: name, surname: surname, email: email) }
}

Basically we take in the two parameter we want to affix and then return another closure (function) that requires the other two parameters. This is used as follows:

let createSprat = createFamilyMember(1, "sprat")
let jack = createSprat("Jack", "[email protected]")
let mary = createSprat("Mary", "[email protected]")

Although we achieve something quite similar to dependency injection, this process still does not completely change the nature of the input; everything is still required all at once; barring the injected values which are entered separately.

Option 3: Currying
In mathematics and computer science, currying is the technique of converting a function that takes multiple arguments (or a tuple of arguments) into a sequence of embedded functions (or closures).

Example:

let createUser = { id in { name in { surname in { email in User(id: id, name: name, surname: surname, email: email) } } } }

Similar to partial application we create a new function that only requires 1 parameter at a time; and after providing for example the id, we are returned another new sequence of embedded functions that now requires only the remaining paramegers 1 at a time.

let createEmployee1 = createUser(1) // returns { name in { surname in { email in User(id: id, name: name, surname: surname, email: email) } } }
let createJack = createEmployee1("Jack") // returns { surname in { email in User(id: id, name: name, surname: surname, email: email) } }

i.e. we have create a function that only requires 1 parameter value at a time; which probably appears a bit pointless at this stage.

Why do we even need Currying
Firstly by reducing a multiple parameter function to a single arity means we can easily merge it with mathematical algebras that typically only use a single arity. Practically though it allows us to enter values at different stages in a process, that might involve different network requests and/or system activities and/or user input.

As for a real example; that'll have to wait for the outcome of this thread; where I plan to demonstrate how input validation is done with this User type and ultimately how parts of the input can be tied to asynchronous processing with e.g. a Future type, both sequentially and multithreaded.


PS. let me know if you'd like to see an example of this in any particular language.

 

[_kabal_]

Nice

Could you talk about the difference in partial application and “decorating”

Eg

val createSprat = { name: String, email: String -> createMember(1, ‘sprat’, name, email) }
val jack = createSprat(‘jack’, ‘[email protected]’)

 

[[)roi(]]

Nice

Could you talk about the difference in partial application and “decorating”

Eg

val createSprat = { name: String, email: String -> createMember(1, ‘sprat’, name, email) }
val jack = createSprat(‘jack’, ‘[email protected]’)

Partial application is all about shared parameters in much the same way that it's done for dependency injection; the parameter values that you enter are however not typically a permanent fixture as it is in your example. I.e. I am able to use the same partial application function for a different id and surname combination.

As to which approach you adopt is going to be determined by the flexibility of the API that you need, and the values you need to pre-inject. Basically both are considered partial application.

Hope that helps?

 

[cguy]

To be frank, I can't really tell what you are asking for in this challenge. A simple interpreter? A code example? If the latter, the questions that follow seem more like a function of the language than a challenge at all.

 

[[)roi(]]

Granted it's very likely obfuscated by all the extended parts (which was a concern); but I tried to consider your previous commentary on the last thread; i.e. That I was unclear about the final outcome.

Plus this branch of functional programming and much of the patterns is quite abstract; meaning the problem is not easily packaged into a "create a program to draw an binary triangle".

Let me try to clarify.

Part 1, simply requires a single higher order function that takes two parameters: an array of single arity functions and an array of values, for example:
even numbers. f(x) = 2.x ~=> f(1) = 2.1 ~=> 2, similarly f(2) = 2.2 ~=> 4; basically if we feed this function an array with only the even function, and another array of integer values 1 though to 5, it will return an array containing the first 5 even numbers.

However considering the container object in this case is an array, we need to cater for the situations where both arrays can be empty, both could contain multiple elments, etc...

The value of this abstract algebra is the ultimate goal I.e how can something so simplistic lead to an improved outcome for staged input validation, parsing, asynchronous processing and eventually multithreaded processes.

 

[[)roi(]]

Some key differences between FP patterns and OOP patterns.

OOP:

• Majority of OOP patterns are a specific solution to a specific problem
• OOP patterns are simple to understand and apply; the complexity if any resides in the construction of the pattern for general reuse, for example: building a dependency injection framework.

FP:

• Majority of the FP patterns like their math counter parts are simple concepts of an abstract nature.
• The difficulty with FP comes with the application, no different to e.g. the practical application of De Morgan's laws for sets and propositions.

When somebody says they are struggling to understand a Monad -- it's not a struggle with the algebra or its construction; but rather how this single abstract and simple concept is not only beneficial but how it can be employed effectively in code to solve many different problems.

So back to the challenge.

• Part 1 is easy inline with its simple but abstract math counterpart.
• The real challenge is with part 2 in figuring out how such a simple concept is not only helpful, but how it can be employed to solve certain problems.

 

[[)roi(]]

Taking into consideration the lack of any attempts at this challenge...

I have decided to kick off with a typical iterative solution for part 1 (in Swift, but I will follow on with a similar solution in Scala (tomorrow) -- as always let me know if you need pointers to achieve the same in another language):

...create a function that can generate output from the composition of 2 arrays...

Part 1 (initial question) -- Ok let's first consider our input:
Array of integer values (1 through to 5)

let rhs = [1, 2, 3, 4, 5] // rhs ⇒ right hand side

Next, our array of single arity functions; or more specifically the even and odd functions:

let lhs = [{$0 *2}, {$0 * 2 + 1}] // lhs ⇒ left hand side

Note: the {...} element in the lhs array is the short form in Swift for a closure (function); in the case $0 refers to the first provided input parameter. To avoid too much confusion I will show a more lengthy example of this below:

// based on the math formula for all even number i.e. 2n
func even(n: Int) -> Int {
  return n * 2
}

// based on the math formula for all odd numbers i.e. 2n - 1 
func odd(n: Int) -> Int { + 1
 return n * 2 - 1
}

// array of functions from Integer (input) to Integer (output)
let lhs = [even, odd]

Next let's write the iterative solution to combine these two functions:

let lhs = [{$0 * 2 - 1}, {$0 * 2}]
let rhs = [1, 2, 3, 4, 5]

var output = [Int]()
for f in lhs {
  for v in rhs {
    output += [f(v)]
  }
}
print(output) // [1, 3, 5, 7, 9, 2, 4, 6, 8, 10, ]

This could be rewritten as the following function:

func compose(_ lhs: [(Int) -> Int], _ rhs: [Int]) -> [Int] {
  var output = [Int]()
  for f in lhs {
    for v in rhs {
      output += [f(v)]
    }
  }
  return output
}

print(compose(lhs, rhs)) // [1, 3, 5, 7, 9, 2, 4, 6, 8, 10]

As you can see the solution is simple; but that's to be expected.

Math based algebras (patterns in OOP speak) are simple but abstract constructions that on the surface can easily be confused for novelty.

To wrap up for tonight. It's important to note that both the lhs and rhs parameters are wrapped in a type; which in this case is an Array, but it could just as easily be an Optional, a Result, a Future or any other container type.

This algebra can be summarised as something that:

• Extracts the elements from each container object.
• Performs a calculation by composing the elements from the two container objects.
• Lastly wraps up the result back into the type of container object

Note: both parameters are wrapped.

Part 1: bonus points (generic version of the function)

// T is our generic type placeholder
func compose<T>(_ lhs: [(T) -> T], _ rhs: [T]) -> [T] { 
  var output = [T]()
  for f in lhs {
    for v in rhs {
      output += [f(v) as! T] // as! in Swift is a forced cast to generic type T
    }
  }
  return output
}

In the above generic version of the code; we had to perform a forced type casting; which naturally is imperfect because it presupposes that the lhs functions will always play nicely. In real code this should be contained by a more typical null validation check in order to safely deal with situations where the output is unexpected.

Btw. There is a far more simpler way to express the internals of this function using higher order functions. I leave that as an open challenge for anyone to try to simplify, or more specifically to make this generic code safe.

As for the extra bonus point of part 1 (identifying this pattern); that question remains open for anyone to answer.

 

[Johnatan56]

Your results are the wrong way around, lhs is uneven.
Pattern would currently 2*n - 1, 2*n? Not sure what you mean by that. You could calculate the xth number by checking if xth number iess than 2*n, if less than n, it's 2*i-1, if more, it's 2*i-n.

Thanks for the post.

 

[[)roi(]]

Scala solutions for Part 1 (similar match up with Swift code):

val lhs = List({n: Int => n * 2 - 1}, {n: Int => n * 2})
val rhs = List(1, 2, 3, 4, 5)

def compose[T](lhs: List[(T) => T], rhs: List[T]): List[T] = { 
  var output = List[T]()
  for (f <- lhs) {
    for (v <- rhs) {
      output = output ::: List(f(v))
    }
  }
  output
}

println(compose(lhs, rhs)) \\ List(1, 3, 5, 7, 9, 2, 4, 6, 8, 10)

Similarly the inner workings of this function can be replaced with a 1 liner (functional code); see if you can figure out what that would be.

 

[[)roi(]]

Your results are the wrong way around, lhs is uneven.
Pattern would currently 2*n - 1, 2*n? Not sure what you mean by that. You could calculate the xth number by checking if xth number iess than 2*n, if less than n, it's 2*i-1, if more, it's 2*i-n.

Thanks for the post.

Good catch; I've updated the code (switch odd & even closures in the lhs array). Btw It's a simple composition of elements from 2 arrays (single parameters functions with Integer values), as you picked up the order does matter, as for the formula:


PS. This is just a rudimentary example to help visualise what this algebra does; it'll become more clear what the benefit of this is when I tackle the practical examples.

 

[Johnatan56]

Good catch; I've updated the code (switch odd & even closures in the lhs array). Btw It's a simple composition of elements from 2 arrays (single parameters functions with Integer values), as you picked up the order does matter, as for the formula:
View attachment 514305

PS. This is just a rudimentary example to help visualise what this algebra does; it'll become more clear what the benefit of this is when I tackle the practical examples.

Thanks for the solutions.
We could also do something along the lines of the following, since it's counting n1, n2, n3, ..., n(last)*2, just jumping positions +5, -4

  public static void main(String[] args) {
        int[] thelist = new int[]{1,2,3,4,5};
        int[] results =  new int[thelist.length *2];

        int i = 0, position = 0;
        while(position < thelist.length){
         results[position] = i;
         position +=5;
         i++;
         results[position] = i;
         position-=4;
         i++;
        }
        System.out.println(Arrays.toString(results));
    }

Not sure if that will run, but think it should give the right result, though wrong way around. Changing it to a for loop jumping through array of the list instead, you could swap i with it and then use a counter to check if/else for whether 1st or second number.

Of course then it doesn't hold in every case with e.g. strings.

 

[_kabal_]

val lhs = List({n: Int => n * 2 - 1}, {n: Int => n * 2})
val rhs = List(1, 2, 3, 4, 5)

def compose[T](lhs: List[(T) => T], rhs: List[T]): List[T] = { 
  lhs.flatmap(x -> rhs.map(x))
}

one-liner, psuedo syntax?

 

[[)roi(]]

Pleasure,
An aspect I probably didn't explain well enough, is that the problem is far more about the pattern than it is about creating the odd / even sequence. That odd / even sequence is however a helpful way to verify the correct operation of the algebra (pattern):

Practically the problem is more about creating a higher order style function that can compose any array of single arity functions with a second array of input values.

Basically the correct operation of the function ensures that both of these examples work, without any further modification to the compose function:

Here FYI is the solution for this algebra in Scala:

def compose[T](lhs: List[(T) => T], rhs: List[T]): List[T] = { 
  var output = List[T]()
  for (f <- lhs) {
    for (v <- rhs) {
      output = output ::: List(f(v))
    }
  }
  output
}

Odd / Even functions composed with Integer values

val lhs = List({n: Int => n * 2 - 1}, {n: Int => n * 2})
val rhs = List(1, 2, 3, 4, 5) 
println(compose(lhs, rhs))

// Output is: List(1, 3, 5, 7, 9, 2, 4, 6, 8, 10)

String functions composed with String names

val lhs2 = List({name: String => name.toUpperCase()}, {name: String => name.toLowerCase()}, {name: String => name.toLowerCase().capitalize})
val rhs2 = List("Jack", "MaRy", "petEr", "ToM")
println(compose(lhs2, rhs2)) 

// Output is: List(JACK, MARY, PETER, TOM, jack, mary, peter, tom, Jack, Mary, Peter, Tom)

 

[[)roi(]]

val lhs = List({n: Int => n * 2 - 1}, {n: Int => n * 2})
val rhs = List(1, 2, 3, 4, 5)

def compose[T](lhs: List[(T) => T], rhs: List[T]): List[T] = { 
  lhs.flatmap(x -> rhs.map(x))
}

one-liner, psuedo syntax?

Congratulations... that's the exact answer that was needed.

To explain this

The map method is a higher order function that allows us to apply a function or a closure to a value. The map like a loop iterates over the list elements in rhs array, applying each to the x element, the x element in this example is a function that similarly like a loop is iterated over by flatMap.

Basically flatMap, iterates over the elements (the functions) in lhs array, whereas map iterates over the values in rhs array. The reason why the outer iteration is a flatMap and not a map is to avoid an array embedded in another array i.e. 2D array.

flatMap, basically performs a map and then flattens the structure, without this the result would be:

List(List(1, 3, 5, ...), List(2, 4, 6, ...)) instead of List(1, 3, 5, ..., 2, 4, 6, ...)

Limitations of the current compose function
The current compose function as it stands has a significant restriction which limits it usefulness in comparison with flatMap and map, that is:

• The compose function expects the same type in and out
• whereas standard forms of flatMap, and map allow us the flexibility of transformation e.g. Integer to String

Making this Algebra more flexible over types (similar to flatMap and map)
This can easily be fixed by making a small change to the function's generic signature, as follows:

def compose[T, U](lhs: List[(T) => U], rhs: List[T]): List[U] = { 
  lhs.flatMap(f => rhs.map(f)) 
}

We have introduced two generic types T and U; which represent the input and output types respectively. This allows to not only perform the compositions of elements in two container types, we now can also transform the types in process, for example:

 case class User(val age: Int, val name: String) 

 val lhs3 = List({user: User => user.name}, {user: User => user.age})
 val rhs3 = List(User(23, "Jack"), User(18, "Mary"), User(31, "Peter"), User(14, "Tom"))
 println(compose(lhs3, rhs3))

// List(Jack, Mary, Peter, Tom, 23, 18, 31, 14)

The above example, uses a data class, that stores both ages and names, using the flexibility of the new generic compose function we are now able to output the ages as an Integer and the names as String, whereas previously we would have be limited to the same output as the input i.e.

User -> User // limitation of using 1 generic type [T]

// however this new change now allows us to have function go from both:
User -> Integer
User -> String

At this stage you should hopefully be seeing some similarities between this algebra and flatMap or map. Which should give you a pointer to finding its name; it's different to map, which is in mathematics known as a functor, and also different to flatMap, which in mathematics is known as a Monad.

i.e. it's something similar but not quite the same.

 

[[)roi(]]

Curried and Partial Functions - Part 2
In many languages we have the ability to manually write functions in their curried or uncurried format, for example:

// uncurried format (i.e. standard format)
def add1(lhs: Int, rhs: Int): Int = lhs + rhs

// curried format
val add2 = (lhs: Int) => (rhs: Int) => lhs + rhs

// alternative scala curried function format
def add3(lhs: Int)(rhs: Int): int = lhs + rhs

Usage examples:

// normal use
println(add1(1, 2)) // parameters provide all at once

println(add2(1)(2)) // parameters provide 1 at a time, can be done over a few code steps.

println(add2(1)(2)) // works the same as add2.

But it's not always practical to rewrite functions in their curried form
Whilst this is easy to do, it isn't always practical to have to rewrite all our functions in the curried format, and what happens we don't want all the parameters to be curried i.e. a combination of partial application and curried.

To get around this issue, we can add some helper functions to our tool belt; functions that can turn a standard function into a curried function and similarly partially apply some of the parameters of any function.
http://scala-lang.org/files/archive/spec/2.11/06-expressions.html#method-values
Curried Helpers:

// curry helpers for 1 through to 4 parameter methods; we can use the same principle to expand this for greater than 4 arity methods.

def curry[A, B](f: (A) => B) = { (a: A) => f(a) }
def curry[A, B, C](f: (A, B) => C) = { (a: A) => (b: B) => f(a, b) }
def curry[A, B, C, D](f: (A, B, C) => D) = { (a: A) => (b: B) => (c: C) => f(a, b, c) }
def curry[A, B, C, D, E](f: (A, B, C, D) => E) = { (a: A) => (b: B) => (c: C) => (d: D) => f(a, b, c, d) }

Usage examples:

println(curry(add1 _)(10)(12))

We basically convert the add1 standard function to its curried version by using the curry function helper.
Note:
[table="width: 100%, class: outer_border, align: left"]
[tr]
[td]The _ underscore symbol in scala is required when assigning a standard method (def) to a variable, or when converting a method to its function equivalent. This difference between function and method stems from Scala's link to Java's bytecode. The underscore symbol essentially transforms the method into a function that can be assigned to variable. This is formally known as ETA Expansion[/td]
[/tr]
[/table]


Partial Application Helpers:

// Similar to the curried helpers, these partial application helpers cater for 2 through to 4 parameters methods where some or all of the parameters are affixed.

def partial[A, B, C](f: (A, B) => C, a: A) = { (b: B) => f(a, b)}
def partial[A, B, C](f: (A, B) => C, a: A, b: B) = { () => f(a, b)}
def partial[A, B, C, D](f: (A, B, C) => D, a: A) = { (b: B, c: C) => f(a, b, c)}
def partial[A, B, C, D](f: (A, B, C) => D, a: A, b: B) = { (c: C) => f(a, b, c)}
def partial[A, B, C, D](f: (A, B, C) => D, a: A, b: B, c: C) = { () => f(a, b, c)}
def partial[A, B, C, D, E](f: (A, B, C, D) => E, a: A) = { (b: B, c: C, d: D) => f(a, b, c, d)}
def partial[A, B, C, D, E](f: (A, B, C, D) => E, a: A, b: B) = { (c: C, d: D) => f(a, b, c, d)}
def partial[A, B, C, D, E](f: (A, B, C, D) => E, a: A, b: B, c: C) = { (d: D) => f(a, b, c, d)}
def partial[A, B, C, D, E](f: (A, B, C, D) => E, a: A, b: B, c: C, d: D) = { () => f(a, b, c, d)}

Usage examples:

val pAdd = partial(add1 _, 3) // returns a new function where the 1st parameter has been partially applied as 3
println(pAdd(7)) // result is 10  (i.e. 3 partially applied + 7)
println(pAdd(17)) // result is 20  (i.e. 3 partially applied + 17)

That's it for currying and partial application for now. This has btw been introduced because the next section of the new algebra will start to compose curried functions with this pattern.

Note:
Nothing prevents us from partially applying some of the parameters of a method, and then currying the remainder. In this way we start to achieve more than what is typically available with dependency injection; but that should hopefully become more evident as we expand on this new algebra in the next part.

 

[[)roi(]]

Review of MAP & FLATMAP

MAP
Like a standard loop iterates over an input list (or any container object) and composes each element with a function, for example:

// let's start by first examining how this would typically be done with iterative code:
val values = List(1, 2, 3, 4, 5)
val odd = (n: Int) => 2 * n - 1
var output = List[Int]()
for (v <- values) {
  output = output ::: List(odd(v))
}
println(output) // List(1, 3, 5, 7, 9)

//Here's the equivalent using map
println(values.map(odd)) // List(1, 3, 5, 7, 9)

Next example: Let's see how we could iteratively recreate the merged list of odd & even numbers.

val values = List(1, 2, 3, 4, 5)
val odd = (n: Int) => 2 * n - 1
val even = (n: Int) => 2 * n
val functions = List(odd, even)
var output = List[Int]()
for (f <- functions) {
  for (v <- values) {
    output = output ::: List(f(v))
  }
}
println(output) List(1, 3, 5, 7, 9, 2, 4, 6, 8, 10)

// Now lets see the same thing using map twice 
println(functions.map(f => values.map(f))) // List(List(1, 3, 5, 7, 9), List(2, 4, 6, 8, 10))

OOPS.... as you can see when we use 2 maps the output is not exactly what we need; the output of the odd and the even functions are contained in sub list elements i.e. a 2D list of results.

To fix this we simply need to substitute flatMap for the outer iteration, which essentially flattens the structure after the mapping, for example:

println(functions.flatMap(f => values.map(f))) // List(1, 3, 5, 7, 9, 2, 4, 6, 8, 10)

Essentially we've recreated what happens with this new algebra, however this version is strictly tied to the monadic behaviour of flatmap which is not always ideal.

Why would we not always want to be tied to flatMap (i.e. a monad)?
To understand this we need to understand the underlying behaviour of a Monad (flatMap), in comparison with a functor (Map), and this new algebra.

I will cover that part this evening with a few examples of where the use of map and flatmap can replace the typical null check boiler plate code that accompanies the use of OOP objects,.

 

[[)roi(]]

Algebra / Pattern's name
This algebra is called an Applicative Functor, or just Applicative, is also sometimes called the functional pearl of FP, because it more flexible than a standard covariant functor (map) and not as restricted as a monad (flatmap).

Let's start by compare the function signatures of these 3 algebras:

     map(f:  (A) ->  B,  v: [A]) -> [B]
      ap(f: [(A) ->  B], v: [A]) -> [B] // applicative method signature
 flatMap(f:  (A) -> [B], v: [A]) -> [B]

Functor (map):
Takes a function (f) from type (A) to another type (B), and iterating over the elements in an array of values (v); compose each element with the function (f).

Applicative (ap):
Takes an array of functions (f) from type (A) to another type (B), and iterating over the elements in an array of values (v); composing each element with each of the functions in (f).

Monad (flatMap):
Takes a functions(f) from type (A) to another an array of type (B), and iterating over the elements in an array of values (v); composing each element with the function (f).

The above descriptions are just as abstract as the algebras upon which they're based; i.e. knowledge of the method signatures alone provides little to no clarity as to why you would favour one over the other, or the specific design advantages of each.

Below I am including references to mathematical discussions of this algebra; however it is not necessary for you to read this in order to understand or take advantage of this algebra, in the same way that most newcomers to FP, never read or understand the maths behind map or flatMap -- why? ... simply said for most use cases its far more important to understand the application of the algebra than it is to understand the math behind this.

The distinction between each of the above three algebras will become more a lot more clear over the next set of posts (Part 2) --- which I should have time to start posting either later tonight or tomorrow.

---

For anyone who prefers to look over the mathematics behind this pattern, you can refer to either of these links for an extensive math centric analysis:

• An in-depth category theory based analysis of Applicative Functors
• Applicative programming with effects: the paper that introduce this algebra

 

[_kabal_]

Awesome stuff, keep it up

 

[[)roi(]]

Part 2 - Using Applicatives
To demonstrate applicatives I'm going to start off by demonstrating how the Applicative Functor (or just Applicative) algebra is implemented for the Option type. The reason for this is fairly simple, because a lot of code has been written to avoid the java.lang.NullPointerException

i.e. a lot of code has been written to validate if an object is instantiated before we attempt to use it.

So how do we deal with Null Pointer Exceptions?
Some languages have very little provision in the compiler for preventing this; whereas Swift and to a lesser degree Scala try to avoid the conditions that feed into this problems, for example:

• Compiler keeps track of variable initialisation, etc.

That doesn't mean that any languages that don't have this, we have to admit failure and continue adorning code with the more typical null safety harnesses, for example:

case class AcmeBox(var value: Int)
var box: AcmeBox = null
// box.value += 1 // java.lang.NullPointerException when attempting to modify an object that is either uninstantiated or null 

// Safer more traditional approach looks a lot like this
 if (box != null) {
   box.value += 1
 }

Summary: we only change the object if it's not null

So what does FP do with Null Pointer Exceptions?
If FP, stemming from Maths we tend to lift most of our elements and computation into conforming containers like: List, Future, ... because by lifting the elements into a container, we can both perform computations, and take advantage of mathematic algebras that the originating element types don't have built-in support for e.g. map, flatMap, etc.

The container types that the rest of this first part is going to focus on is the Option type; a type that is designed to deal with the same problems as null pointer exceptions.

Re-implementing the AcmeBox example using an Option type

case class AcmeBox(var value: Int)
val box2 = Some(AcmeBox(14)).map(b => AcmeBox(b.value + 1)) // Option[AcmeBox]
println(s"box2 = ${box2}") // Some(AcmeBox(15))

FP computation is built around two things, a container type like Option that either has Some data or None; none being the equivalent of null. The map method internally allows us to compose a function / closure with any valid element in the container, and similarly to the "if null" boilerplate it avoids trying to compose functions with invalid elements.

Summary: Conceptually the map has the "if null" check built-in so the typical boilerplate code required for java.lang.NullPointerException is no longer required.

Option Chaining
FP computations using algebras like map and flatMap typically the involve chaining of computations; some which are strictly sequential, others asynchronous and yet others commuted in parallel.

Here's an example of a chain computation involving both map and flatMap:

val valueSome: Option[Int] = Some(1)
valueSome
  .map(v => v + 1)
  .debug() // Debug ~> Some(2) : map valueSome
  .flatMap(v => if(v % 2 == 0) None else Some(v))
  .debug() // Debug ~> None : flatMap valueSome

Note:
[table="width: 100%, class: outer_border"]
[tr]
[td]In the above example, I have inserted an inline chained method called debug(...), which is a simple none effectual method that allows us to print out value of elements in a computation chain, code included below:
[/td]
[/tr]
[/table]

implicit class OptionDebug[T](lhs: Option[T]) { 
  def debug(comment: String = ""): Option[T] = {
    lhs match {
      case Some(value) => println(s"Debug ~> Some(${value}) : ${comment}")
      case _ => println(s"Debug ~> None : ${comment}")
    }
    lhs
  } 
}

Adding the Applicative Algebra to the Option type
The Scala Option type like List has built-in support for map (functor) and flatMap (monad), but not for Applicative Functor. However this like we did for List, is fairly easy to add, here's the code for that:

implicit class OptionApplicativeMethod[T, U](lhs: Option[(T) => U]) { 
  def ap(rhs: Option[T]): Option[U] = {
    lhs.flatMap(f => rhs.map(f))
  }
}

Note: The method name ap is short for applicative. This code btw is the approach that Scala takes to add method extensions to existing types. This is not too different to the way in which this is done in Swift or C#, ...

Example of using applicative with Option type
Let's start with a very simplistic example of a function that adds two integers together. Let's define that function:

def add(lhs: Int, rhs: Int): Int = lhs + rhs

Normally we use this add function like this:

add(1, 2) // 3

Using the applicative algebra we can change the computation into a left to right chained process like this:

Some((add _).curried)
  .ap(Some(1))
  .ap(Some(2))
  .debug("Applicative Add") // Debug ~> Some(3) : Applicative Add

Here's an explaination of the above -- similar to map and flatMap, we need to lift our elements into our applicative container type, which in this case is Option; to add some element we use the Some type which is a subtype of Option when it contains a valid element; next applicative like map and flatmap, require that the wrapped function is single arity, which of course the add method is not; it has 2 parameters.

To get around this problem we curry the add method, which turns it into a series of single arity functions, one embedded inside another. Then if you remember every ap method requires two things a function and a value; both of which in this case must have been lifted into the Option type container object (see this post for a quick review).

This first value (1) is passed to the curried form of add, which then returns a new function that now only requires the second value, the second ap chained method call provides this value (2), and finally the computation is performed, similarl to map on List; this chained computation of add is returned as value still wrapped in Option (the container type)

Why we would ever want to do this will not be clear at this point, so don't be concerned if you're having a WTF moment.

The real value of this will start to become apparent in the next few posts.