• You are not registered on MyBroadband, which means you miss out on great benefits. To join our community is very easy, and completely free. Register now.
  • New Two-Day Giveaway - Enter Here

Another Functional Programming Challenge

_kabal_

Expert Member
Joined
Oct 24, 2005
Messages
2,490
#21
for those maybe more familiar with JavaScript, Promise is very much like Option. It is both a functor and a monad. The method then behaves the same as both map and flatmap

Code:
const promise = asyncOperation(); // Promise<number>
promise
   .then(x -> x + 1) //map - returns a Promise<number> 
   .then(toStringAsync) //map - toStringAsync(number) returns a Promise<String>, so this returns Promise<Promise<String>>
   .then(x -> console.log(`your lucky number is ${x}`)); //flatmap - no need to unbox the promise returned by toStringAsync(num)
 
Last edited:

kfc4unme

Well-Known Member
Joined
Dec 27, 2016
Messages
302
#22
To the OP, I'm enjoying this. I am interested in getting to know more about functional programming. Just curious about you, you seem to know allot of languages - what is your story?

I've been mainly a java dev for years now (dipping my toes in JS, c++, scala but nothing hectic). I'm keen to play with a new language. I am thinking Kotlin - what do you think?
 

[)roi(]

Executive Member
Joined
Apr 15, 2005
Messages
5,579
#23
for those maybe more familiar with JavaScript, Promise is very much like Option. It is both a functor and a monad. The method then behaves the same as both map and flatmap

Code:
const promise = asyncOperation(); // Promise<number>
promise
   .then(x -> x + 1) //map - returns a Promise<number> 
   .then(toStringAsync) //map - toStringAsync(number) returns a Promise<String>, so this returns Promise<Promise<String>>
   .then(x -> console.log(`your lucky number is ${x}`)); //flatmap - no need to unbox the promise returned by toStringAsync(num)
Exactly, many of the more interesting and powerful types are constructed on these simple / abstract algebras.

Monad btw implements both the axioms (rules) of a functor and applicative; however as you'll hopefully see in my next set of posts: monads are strictly limited to state (tracking through first point of failure), whereas a more flexible structure like applicative allows us to track multiple failures, and also perform these actions in parallel.

Promise and Future is quite similar in design I.e. They both hold onto a computation and allows us to apply additional map/flatmap composites on top of this computation. For the C# guys, Async returns a Task; which is just another name for a Future, and a modified form of Task enables parallel processing, via this Applicative algebra.

For those following along: Later this thread I'll be demonstrating the basics of a future type (build your own) and how it can be enhanced with applicative for not only asynchronous processing but also parallel processing.

As for Javascript; everything that I've presented so far is quite easy to replicate in JS, so just ask if you need any pointers.
 
Last edited:

[)roi(]

Executive Member
Joined
Apr 15, 2005
Messages
5,579
#24
To the OP, I'm enjoying this. I am interested in getting to know more about functional programming. Just curious about you, you seem to know allot of languages - what is your story?

I've been mainly a java dev for years now (dipping my toes in JS, c++, scala but nothing hectic). I'm keen to play with a new language. I am thinking Kotlin - what do you think?
Glad this thread is interesting... and hopefully the conclusion to this thread is enough of an enticement to others to not only learn about FP but programming technique in general.

Kotlin is a new and exciting JVM based language, and all the techniques I am presenting here can fairly easily be applied to Kotlin code, however to be honest it's not always as seamless to do versus languages like Scala, Swift and others.

This lack of seamlessness only really relates to the amount of code you'll have to repeat (i.e. boiler plate). Kotlin is however a relatively fast evolving language so I'd expect that most of these limitations to be overcome quite soon. So please don't let that stop you from learning Kotlin; like Swift it's a very exciting new age language to add to your tool belt.

[HR][/HR]
As for me; I've been programming for well over 3 decades; started out as a child in Basic on a TI-99/4A; and grew my understanding from there. For the most part of my life I prioritised working over any formal study... and the lack of degree didn't really impact my ability to secure employment across the US, UK, France and Germany for a large part of two decades.

As for studies.
Although most of my experience is not classically obtained; I have subsequently completed both undergraduate and post graduate degrees and I'm busy with a part-time PHD in language studies (compilers). This was spurred on by both extra free time and because in number of cases how you appear on paper helps when it comes to competing for a contract remotely.

In my spare time i.e. when I'm not behind a keyboard; I'm either busy tutoring a select group of students, or busy with some micro-farming.
 

[)roi(]

Executive Member
Joined
Apr 15, 2005
Messages
5,579
#26
Applicative example - registration form validation
Let's define a simplified class to represent a few fields rudimentary fields on a registration form; less fields to keep the code blocks small, because this is more about the technique that the applicative makes possible, than the accuracy of fields that many registration form employ.
PHP:
case class Account(val id: Int, email: String)
Example of applicative data entry
PHP:
Some(Account.curried)
  .ap(Some(1))
  .ap(Some("jack@nofat.com"))
  .debug("Method") // Debug ~> Some(Account(1,jack@nofat.com)) : Method
We lift a curried form of the Account initialiser method into a Option using Some; because of our ap method, we can now left to right add the Account parameters in much the same way as we did with the add function, finally ending up with an instantiated object wrapped in an Option.

Applicative also gives a fail-able initialiser for free
PHP:
pure(Account.curried)
  .ap(None)
  .ap(pure("jack@nofat.com"))
  .debug("Method") // Debug ~> None : Method
If any of the account values were to be invalid i.e. None (or null); the result would be an Option type wrapping None (null). Basically this approach always wraps failures in order to safely deal with them later, as opposed to throwing an exception or crashing the program with an unmanaged null pointer exception.

In the next post we are going to start adding validation to values i.e. did the user enter what was expected.

Optional information about lifters
[HR][/HR]Before that I'd like to provide some additional explanation about the Some lifting types that Scala uses to wrap element values in an Option type.

Note:
[table="width: 100%, class: outer_border"]
[tr]
[td]The Some type in Scala lifts an element into a container type like Option; these container types serve the purpose of making it easier to apply math type operations (map, flatMap, ...) to our elements (data), but also to add certain behaviours e.g. better handling of Null Pointer Exceptions
[/td]
[/tr]
[/table]

In other applications of the Applicative algebra we typically define a lifting function called pure that can lift any value into our container type, for example in Haskel the Applicative is defined as follows:
PHP:
class Functor f => Applicative f where
  pure  :: a -> f a
  (<*>) :: f (a -> b) -> f a -> f b
Don't worry if you can't read Haskell code; I'll step you through it. First thing, a class is the definition for a type; similar to an interface or trait in other languages (any other differences don't matter here).

The inheritance of features works left to right i.e. the class signature states that Applicative is a Functor (i.e. it must also implement the map method).

Next is pure; this is a function signature, i.e. without the implementation. Think of it as something similar to an interface or trait for functions. Basically we take a generic value of type 'a' and lift it into a functor of type 'f'. Note: that both Functor and Applicative have been assigned a generic placeholder variable 'f' i.e.
  • class Functor f => Applicative f where
This pure function is our lifter, and does the same job as Some or None for the Scala Option type. i.e. we embed an element in an Option type.

Next is (<*>) -- this is just the way that Haskell uses to define the signature for a custom operator i.e. <*>is synonymous with our function ap. i.e. we have a computation from generic type a to b wrapped in a functor f which then takes another value a also wrapped in a functor f and returns the result b also wrapped in a functor f. i.e. this is the same as the signature for Applicative I summarised in this post:
Custom Operator Note:
[table="width: 100%, class: outer_border"]
[tr]
[td]Because Scala can also support custom operators; For interests sake I will also include a separate post, on how we can define and implement this Applicative operator <*> in Scala to be used as an alternative to the dot method chaining of the ap method.[/td]
[/tr]
[/table]
 
Last edited:

[)roi(]

Executive Member
Joined
Apr 15, 2005
Messages
5,579
#27
Haskell Style <*> applicative operator

To avoid repeating the internal workings of this operator; I'm going to make it call the original ap method we defined for the Option type. So for clarity's sake I will again include the ap method definition to better show this relationship.

Option's ap method
PHP:
implicit class OptionApplicativeMethod[T, U](lhs: Option[(T) => U]) { 
  def ap(rhs: Option[T]): Option[U] = {
    lhs.flatMap(f => rhs.map(f))
  }
}
Next let's define our custom applicative operator <*>
PHP:
implicit class OptionApplicativeOperator[T, U](lhs: Option[(T) => U]) {
  def <*>(rhs: Option[T]): Option[U] = {
    lhs.ap(rhs)
  }
}
Ok let's now us this to recreate the solution from the last post i.e. the instantiation of an Account using the typical left to right signature that applicative affords us.

PHP:
Some(Account.curried) <*> Some(1) <*> Some("jack@nofat.com")
Which can also be reformatted as follows:
PHP:
(Some(Account.curried) 
  <*> Some(1) 
  <*> Some("jack@nofat.com"))
.debug("Operator") // Debug ~ Some(Account(1,jack@nofat.com))
Note:
We had to surround the Account instantiation in an extra set of brackets to ensure that the outcome of this composition is passed to the debug method i.e. not just the last Some. FYI Haskell has a number of ways to avoid these types of brackets i.e. simpler control over operator associativity.

Preference for either "dot method" or "operator composition"
As to whether you prefer to use dot method chaining or operator composition is really left up to personal preference in languages like Scala and Swift because they support both options.

And if you wondering about map; yes even it has a special operator in Haskell: <^> and flatmap is >>=

Btw for those exploring Kotlin; custom operators are not currently supported, but infix functions are, so in Kotlin the above code would typically look something like this using infix function composition:
PHP:
Some(curry(Account)) ap Some(1) ap Some("jack@nofat.com")
i.e. the ap infix function is being used in the same way as the <*> operator. Again personal preference will decide which approach you prefer, because Kotlin supports dot method chaining as well.
 
Last edited:

[)roi(]

Executive Member
Joined
Apr 15, 2005
Messages
5,579
#28
Let's add some input validation
Our input validation in this example is going to be represented as two very simplistic methods determine if the values enter by our user is correct or not.

PHP:
[PHP]
def validate(id: Int): Option[Int] = {
  return if(id > 0) Some(id) else None
} 

def validate(email: String): Option(String) = {
  return if(email contains "@") Some(email) else None
}
As you can hopefully see, we deem all id values of greater than zero to be valid, and all email addresses containing an @ sign to be also valid. Very simplistic but it should help to get the idea across.

Note: both of these methods act a lifters i.e. the results are returned as an Option type

Ok let's merge this in with our applicative instantiation
PHP:
// Successful validation
Some(Account.curried)
  .ap(validate(1))
  .ap(validate("wife@eatnolean.com"))
  .debug("Method") // Debug ~> Some(Account(1,wife@eatnolean.com)) : Method

// Incorrect ID
Some(Account.curried)
  .ap(validate(0))
  .ap(validate("wife@eatnolean.com"))
  .debug("Method") // Debug ~> None : Method
The above validation fails as expected when the input data is invalid; but a None return like a null is typically worthless, because it provides us no way to indicate to the user what was wrong.

This is a limitation of the Option type; it only allows us to either store Some value or None, in much the same way that null pointer exceptions are binary outcomes, either it works or it doesn't.
 

[)roi(]

Executive Member
Joined
Apr 15, 2005
Messages
5,579
#29
So the question now is how do we make this better?
Introducing Scala's Either type, which sometimes is also called a Result type.

Either unlike Option, allows us to specify two generic types, which its wraps as either Left or Right. The word right is more typically used to indicate correctness, and inversely the left is wrong. Ps. this isn't politics.

Either type to keep track of errors
The either type is typically used when we need to keep track of two possible outcomes, entitled Right implying success and Left implying failure; the benefit is that we statically type the left and right, for example:
  • Right will store the Account type
  • Left will store a String describing the validation errors

Ok let's create the applicative method for Either, again Scala itself has already ensured that the Either type supports both map and flatmap.

First off lets make Either comply with the Applicative method:
PHP:
implicit class EitherApplicativeMethod[E, T, U](lhs: Either[E, (T) => U]) { 
  def ap(rhs: Either[E, T]): Either[E, U] = {
    lhs.flatMap(f => rhs.map(f))
  }
}

// Let's also add the debug method to easily examine the values in process, when needed (not for production code)
implicit class EitherDebug[E, T](lhs: Either[E, T]) { 
  def debug(comment: String = ""): Either[E, T] = {
    lhs match {
      case Right(r) => println(s"Debug ~> Right(${r}) : ${comment}")
      case Left(l) => println(s"Debug ~> Left(${l}) : ${comment}")
    }
    lhs
  } 
}
The variable placeholders above can be described as follows:
  • E is for Errors
  • T is for the initial type
  • U is for the outcome of the Applicative computation
Note: Any variables or words can typically be used for this. Basically whatever makes sense for you.

Now let's redefine our validation methods to work with the Either type:
PHP:
def validate(id: Int): Either[String, Int] = {
  return if(id > 0) Right(id) else Left("Invalid ID")
} 

def validate(email: String): Either[String, String] = {
  return if(email contains "@") Right(email) else Left("Invalid EMAIL")
}
As you can see we now can map the outcomes to the Right or Left lifters i.e. when it's outcome is correct we return a Right together with the input value, and when it's incorrect we return a Left with the error message as a String

Ok let's see this in action
PHP:
Right(Account.curried)
  .ap(validate(0))
  .ap(validate("wife@eatnolean.com"))
  .debug("Method") // Debug ~> Left(Invalid ID) : Method

Right(Account.curried) 
  .ap(validate(3))
  .ap(validate("jacksprat.com"))
  .debug("Operator") // Debug ~> Left(Invalid EMAIL) : Operator

Right(Account.curried)
  .ap(validate(4))
  .ap(validate("wife@eatnolean.com"))
  .debug("Method") // Debug ~> Right(Account(4,wife@eatnolean.com)) : Method
Cool... now when a validation fails we are returned more than just a None, we have a left Either that contains the String error message of what went wrong. i.e. Something to feed back to the user.

What happens when the User makes more than 1 mistake?
Let's try that...
PHP:
Right(Account.curried)
  .ap(validate(-1))
  .ap(validate("wife+eatnolean.com"))
  .debug("Method") // Debug ~> Left(Invalid ID) : Method
Oops... although there are clearly two capture errors, but we are only returning this first error, why?

The reason for this behaviour stems from our choice to use a flatmap (monad) is the construction of our applicative ap method. By design the flatmap (monad) computation is designed for state i.e. where tracking the sequence of events is important.

For example: if we try to open a file and it fails; there is no sense in trying to read it. Hence in Haskell IO (input/output) processes are typically modelled as Monads.

PHP:
implicit class EitherApplicativeMethod[E, T, U](lhs: Either[E, (T) => U]) { 
  def ap(rhs: Either[E, T]): Either[E, U] = {
    lhs.flatMap(f => rhs.map(f))
  }
}
Basically the lhs.flatMap is limiting us from achieving concurrency in the Applicative, because by algebraic design it stops the computation after the first error.

In this case we are less concerned about sequence and more concerned about trapping all of the capture errors so that we don't frustrate our end user too much with a repeating process of error discovery, for example:
  • They fix one error only to find there is another, ... and another, ... as opposed to the validation providing all the errors at the same time.
In the next post, I will show you how we can modify the applicative method to trap all the errors, or more specifically how we can design the ap method without the use of flatmap to enable this concurrency.
 
Last edited:

[)roi(]

Executive Member
Joined
Apr 15, 2005
Messages
5,579
#30
Modifying the Applicatve ap method to expose concurrency:
The previous rendition of the Either allowed us to trap an error type; in the Left branch of an Either type, which was an improvement over the Option type's binary "it worked" or "it failed" output, however even switching to an Either type ended up with us only being able to expose the first error that occurred as opposed to concurrently examining all paths to expose all the input errors.

This limitation was artificially introduced because we had built the Applicative ap method using flatmap, an algebraic design that is beneficial to maintain state, but when used for an Applicative only limits its versatility.

[table="width: 100%, class: outer_border"]
[tr]
[td]Naturally the problem was approached this way in order to provide you with extra some insight into a key difference between Monad and the Applicative algebras.[/td]
[/tr]
[/table]

Ok enough of the preface, let modify our ap method to enable concurrency.
Ok so to solve this problem; it should be fairly obvious that we need to replace this monad (flatmap) code with some that's more Applicative. I going to use Scala's pattern matching for this, however this can quite easily be replaced with a fairly standard set of if statements for languages that don't support pattern matching.

Note: C#, Kotlin, Scala, Swift, and many others have built-in support for pattern matching.

Here's my first run at this:
PHP:
implicit class EitherApplicativeMethod[E, T, U](lhs: Either[E, (T) => U]) { 
  def ap(rhs: Either[E, T]): Either[E, U] = {
    (lhs, rhs) match {
      case (Right(success), _) => rhs.map(success)
      case (Left(fail), Right(_)) => Left(fail)
      case (Left(fail1), Left(fail2)) => Left(fail1)
    }
  }
}
Reviewing the above code you should firstly see that flatmap has been replace with a typical pattern match of different outcomes of lhs and rhs:
  • 1st pattern match: left hand side (lhs) of the computation is a success (Right) and the right hand side (rhs) can be anything else (underscore is a wildcard match). In this case we do standard functor map; similar to the internals of the previous flatmap applicative.
  • 2nd pattern match: left hand has failed and the right hand side is a success, but we can ignore the associated value; in a failure scenario we're only interested in the failure i.e. Left Either.
  • 3rd pattern match: both side have failed; for now to replicate the flatmap behaviour we are only capturing the 1st failure.
Note:
[table="width: 100%, class: outer_border"]
[tr]
[td]The variable success, fail, fail1, fail2 in the pattern match is called an associative variable and it contains the value stored in the branch of the Either, so if you are using standard if statements, you must remember to first extract these wrapped values; whereas Scala's pattern matching does it automatically for us.[/td]
[/tr]
[/table]

Ok let's rerun our validate code:
PHP:
Right(Account.curried)
  .ap(validate(-1))
  .ap(validate("wife+eatnolean.com"))
  .debug("Method") // Debug ~> Left(Invalid ID) : Method
As you can see we have simply duplicated the outcome for the flatmap version, however a simple change can allow us access to the last failure as opposed to the first one:
PHP:
implicit class EitherApplicativeMethod[E, T, U](lhs: Either[E, (T) => U]) { 
  def ap(rhs: Either[E, T]): Either[E, U] = {
    (lhs, rhs) match {
      case (Right(success), _) => rhs.map(success)
      case (Left(fail), Right(_)) => Left(fail)
      case (Left(fail1), Left(fail2)) => Left(fail2)
    }
  }
}
All we've done is replace Left(fail1) in the 3rd pattern match with Left(fail2), and now the run this code returns only the last error that occurred:
PHP:
Right(Account.curried)
  .ap(validate(-1))
  .ap(validate("wife+eatnolean.com"))
  .debug("Method") Debug ~> Left(Invalid EMAIL) : Method
This is still of course still not perfect as we really want to trap all the errors and not only the last or first error. i.e. essentially we need a list of all the errors.

So let's just add them together
You probably like me would immediately say, let's just add fail1 and fail2 together, both being Strings this should work just fine. For example:
PHP:
implicit class EitherApplicativeMethod[E, T, U](lhs: Either[E, (T) => U]) { 
  def ap(rhs: Either[E, T]): Either[E, U] = {
    (lhs, rhs) match {
      case (Right(success), _) => rhs.map(success)
      case (Left(fail), Right(_)) => Left(fail)
      case (Left(fail1), Left(fail2)) => Left(fail1 + fail2)
    }
  }
}
However we get the following error:
PHP:
error: type mismatch;
 found   : E
 required: String
        case (Left(fail1), Left(fail2)) => Left(fail1 + fail2)
                                                        ^
This basically doesn't work, because of our generics; how must Scala know that our generic type E will support the addition (+) operator. Simply said it needs more guarantees that this is possible.

In the next post I will show you how we can provide these guarantees to the Scala compiler.
 
Last edited:

[)roi(]

Executive Member
Joined
Apr 15, 2005
Messages
5,579
#31
Resolving our generics problem
So we need a way to overcome our problem with the Scala compiler not knowing how to add together a generic type E; a generic placeholder that could be any type, and we can't just assume it will support either the + operator or another concatenation method.

So how do we fix this?

A simple solution is to wrap our generic E in a container type that supports this
Considering we want to keep track of more than 1 failure; essentially a list of failures; the List type seems like an appropriate wrapper for our generic E. Here's the modifications to support this:
PHP:
implicit class EitherApplicativeMethod[E, T, U](lhs: Either[List[E], (T) => U]) { 
  def ap(rhs: Either[List[E], T]): Either[List[E], U] = {
    (lhs, rhs) match {
      case (Right(success), _) => rhs.map(success)
      case (Left(fail), Right(_)) => Left(fail)
      case (Left(fail1), Left(fail2)) => Left(fail1 ::: fail2)
    }
  }
}

def validate(id: Int): Either[List[String], Int] = {
  return if(id > 0) Right(id) else Left(List("Invalid ID"))
} 

def validate(email: String): Either[List[String], String] = {
  return if(email contains "@") Right(email) else Left(List("Invalid EMAIL"))
}
Let's see that in use with multiple validation faults;
PHP:
Right(Account.curried)
  .ap(validate(-1))
  .ap(validate("wife+eatnolean.com"))
  .debug("Method") // Debug ~> Left(List(Invalid ID, Invalid EMAIL)) : Method
... and there we have it an Applicative method that enables concurrency. As for the use of List to overcome the generic constraints; this is not the only way to do this, a more robust way to support this would be to constrain this to another algebra called Semigroup, which is a pattern specifically designed for the combining of types, which some languages define as a trait / interface called Addable -- but that's for another time and another thread.

Hope you're at least starting to see the value of this simple, but abstract pattern, and that I've also removed a little of the mystery behind functor (map) and monad (flatmap) patterns.

Next post in this thread will examining the Future type and how it can be enhanced with conformance to the Applicative algebra. I'll post this during the course of the coming week., but feel free to experiment with this yourselves, and post any observations that you have realised about the patterns or alternatively try your hand at creating a Future type that incorporates this pattern and employs it for parallel operations i.e. splitting computations across multiple threads.
 
Last edited:

[)roi(]

Executive Member
Joined
Apr 15, 2005
Messages
5,579
#32
Btw for those who have found value in this thread; remember what I have shown has little to do with a requirement for strict naming conventions or the insistence on math speak or anything pedantic. APIs are always a bit of personal taste and group vote; so whilst they all be centred on the same underlying mathematical concepts, it is not at all important that the API strictly follow the Haskell naming convention, for example:
  • instead of using .ap as the method name for the Applicative chaining, we could equally choose more friendlier names like .with, or .bind, or .<insert you verb of choice>...
  • Consider for example C# Linq; which is just a name for a collection of FP algebras; for example Select is just another name for map and SelectMany is just another name for flatMap, ...

API example (dot chaining syntax):
PHP:
  createAccount
    .bind(Valid.Account.id(1))
    .bind(Valid.Account.email("wifeeatnolean.com"))
    .bind(Valid.Account.name("wife"))
    .debug("Method") // Debug ~> Left(List(Invalid EMAIL)) : Method
API example (operator composition syntax):
PHP:
  (createAccount 
    <*> Valid.Account.id(-1)
    <*> Valid.Account.email("wife+eatnolean.com") 
    <*> Valid.Account.name("Jac"))
    .debug("Method") // Debug ~> Left(List(Invalid ID, Invalid EMAIL, Invalid NAME)) : Method
Remember the purpose of this thread and the previous one is far more about learning technique, and the many different ways to tackle computing challenges. Let me know if you'd like to see another use case for Applicatives, there are like map many examples of where these very simple and abstract algebras can provide us with alternative ways to approach many problems.

Ps. I'm working on translating my Swift code for Futures to Scala; re there was an interest shown early in this thread for Scala, and hence I've driven most of the code around that; however I'm open to using another language for future threads or just to demonstrate more FP technique; so just ask if you you'd like to see a focus on another language, especially one you're more comfortable with.
 
Last edited:

[)roi(]

Executive Member
Joined
Apr 15, 2005
Messages
5,579
#33
Future
Futures and Promises originated in functional programming and are used to decouple a value (a future) from the process of its computation (a promise); essentially a Future is a type that holds onto a computation; but is more typically used for some type of asynchronous request, for example:
  • retrieving something over the network
  • execution of dependency based and /or long running style of computations
The reason I'm going to quickly review the basic construction of a Future type is to show with some similarity to List, Option and Either types, how the Applicative algebra is integrated with Futures, and then hopefully to show how this is an enabler concurrent asynchronous computations.

Ok so let's build our first Future type...
PHP:
case class Future[T](val f: ((T) => Unit) => Unit)
We define a generic case class of type T, that takes a computation:
  • T to Unit
Which in turn is function signature (T => void) returning a void, which is essentially similar to an effectual method, except here we use the wrapping of a value type T in an effectual (action) method to hold onto this wrapped computation.

Note:
[table="width: 100%, class: outer_border"]
[tr]
[td]
Unit in Scala is the equivalent of void
Another way to think of a Future as a function wrapped in a function, this wrapped computation is what we hold onto.
[/td]
[/tr]
[/table]

Ok so let's define our lifter function
To lift a value and/or computation into our Future type.
PHP:
def pureFuture[T](v: T): Future[T] = { 
  Future[T]({ f => f(v) })
}
Now for example we can use this function to lift any value into a Future, let's lift the integer value 1:
PHP:
pureFuture(1)
What's missing is a way to access this value in our Future i.e. we need a method that allows us to do something with it.

Let's define a Future method extension for this called onResult
PHP:
implicit class FutureOnResultMethod[T](lhs: Future[T]) { 
  def onResult(callback: (T) => Unit): Unit = {
    lhs.f(callback)
  }
}
Basically we have a method that takes a closure or an effectual function from type T to void (unit), and by accessing our instance (self), which is the parameter lhs, we can pass our callback closure to the original wrapping value (as a computation). Which then allow us to for example print out the value that was wrapped by our Future:
PHP:
pureFuture(1)
  .onResult(v => println(v)) // 1
Now let's make our Future a functor (i.e. add the map method)
PHP:
implicit class FutureFunctorMethod[T](lhs: Future[T]) { 
  def map[U](g: (T) => U): Future[U] = {
    Future[U]({ f => lhs.onResult({ x => f(g(x))}) })
  }
}
So x is our internal future value accessible from within our Future's onResult method (lhs is a reference to self), which is then composed with our new map's transform g from (T to U), and then finally composed together with our new result Future's f re (T to void)

Ok let's see map in use:
PHP:
pureFuture(1)
  .map(v => v + 1)
  .onResult(v => println(v)) // 2
Now let's make our Future a monad (i.e. add the flatMap method)
PHP:
implicit class FutureMonadMethod[T](lhs: Future[T]) { 
  def flatMap[U](g: (T) => Future[U]): Future[U] = {
    Future[U]({ f => lhs.onResult({ x => g(x).onResult(f) }) })
  }
}
So again x is our internal future value accessible from within our Future's onResult method (lhs is a reference to self), which is then composed with our new flatMap's transform g from (T to Future), and because the result is Future, we need to us it's onResult method to compose this together with our new Future's f re (T to void)

Ok let's see flatMap in use:
PHP:
pureFuture(3)
  .map(v => v * 4)
  .flatMap(v => pureFuture(if(v % 2 == 0) "even" else "odd"))
  .onResult(v => println(v)) // even
In the next post we look at making this Future type into an Applicative, and look at some basic usage examples, thereafter we move onto exploring concurrent asynchronous processing that our Applicative algebra affords us when we decouple it from flatMap (Monad) -- i.e. as we did with the Either type to concurrently record all the input validation errors as opposed to just the first one. .
 
Last edited:

[)roi(]

Executive Member
Joined
Apr 15, 2005
Messages
5,579
#34
Future as an Applicative
Here's to the code to add the Applicative algebra to our Future type. Initially we have this linked to flatMap for convenience and then enhance it for concurrency in the next article.
PHP:
implicit class FutureApplicativeMethod[T, U](lhs: Future[(T) => U]) { 
  def ap(rhs: Future[T]): Future[U] = {
    lhs.flatMap(f => rhs.map(f))
  }
}

implicit class FutureApplicativeOperator[T, U](lhs: Future[(T) => U]) { 
  def <*>(rhs: Future[T]): Future[U] = {
    lhs.ap(rhs)
  }
}

implicit class FutureApplicativeBind[T, U](lhs: Future[(T) => U]) { 
  def bind(rhs: Future[T]): Future[U] = {
    lhs.ap(rhs)
  }
}
This allows use to write the following code:
PHP:
pureFuture((add _).curried)
  .ap(pureFuture(2))
  .ap(pureFuture(3))
  .onResult(f => println(f)) // 5

(pureFuture((add _).curried) 
  <*> pureFuture(2) 
  <*> pureFuture(3))
  .map(v => v * 9)
  .onResult(f => println(f)) // 45
Challenge:
Can you get our Either input validation shown below to work with our new Future type?
PHP:
createAccount
  .bind(Valid.Account.id(4))
  .bind(Valid.Account.email("wifeeatnolean.com"))
  .bind(Valid.Account.name("wif"))
  .debug("Method") // Debug ~> Left(List(Invalid EMAIL, Invalid NAME)) : Method
 

[)roi(]

Executive Member
Joined
Apr 15, 2005
Messages
5,579
#35
Ok let's wrap up... firstly let's look an a few examples of how the Account input validation can be use in conjunction with our Future type:

Lifting our Either Applicative operator composition into a Future
PHP:
pureFuture(createAccount 
  <*> Valid.Account.id(-1) 
  <*> Valid.Account.email("jackienolean.com") 
  <*> Valid.Account.name("Jackie"))
  .onResult(v => println(v)) // Left(List(Invalid ID, Invalid EMAIL))

// Alternative simplify the Either Account validation applicative by compositing it into a new function
val createValidAccount = (id: Int, email: String, name: String) => 
  (createAccount <*> Valid.Account.id(id) <*> Valid.Account.email(email) <*> Valid.Account.name(name))

// Using a new composition that creates a new Account after validation on the input
pureFuture(createValidAccount(1, "jack@nofat.com", "jack"))
  .onResult(v => println(v)) // Right(Account(1,jack@nofat.com,jack))
Lifting our Either createAccount Either Applicative into a Future and then mapping over the validations
PHP:
// Method chaining is used in conjunction with Futures map method to validate input
pureFuture(createAccount)
  .map(e => e.bind(Valid.Account.id(-1)))
  .map(e => e.bind(Valid.Account.email("wife@nolean.com")))
  .map(e => e.bind(Valid.Account.name("Jac")))
  .onResult(v => println(v)) // Left(List(Invalid ID, Invalid NAME))

// Operator composition is used in conjunction with Futures map method to validate input
pureFuture(createAccount)
  .map(e => e <*> Valid.Account.id(-1))
  .map(e => e <*> Valid.Account.email("wife@nolean.com"))
  .map(e => e <*> Valid.Account.name("Jackie"))
  .onResult(v => println(v)) // Left(List(Invalid ID))
 

[)roi(]

Executive Member
Joined
Apr 15, 2005
Messages
5,579
#36
Using Applicative algebra to enable multi-threaded concurrency
Ok to wrap up, let's look at how we can add multi-threading concurrent into our Future type; so that two or more calls can be run at the same time, all the while preserving the composition of the all of the parts, as we achieved with the Either's type's concurrent input validation. The only major difference here is that Future style computations can take significantly longer to process, for example they might be computational intensive and/or network dependant, or a combination of both.

Ok before we jump in let's reaffirm what our Future's applicative method currently looks like:
PHP:
// our base method extension; Note: that the internal computation is still monadic i.e. it uses flatMap
implicit class FutureApplicativeMethod[T, U](lhs: Future[(T) => U]) { 
  def ap(rhs: Future[T]): Future[U] = {
    lhs.flatMap(f => rhs.map(f))
  }
}

// Our operator for operator composition, calls into the base extension method
implicit class FutureApplicativeOperator[T, U](lhs: Future[(T) => U]) { 
  def <*>(rhs: Future[T]): Future[U] = {
    lhs.ap(rhs)
  }
}

//alternative API, calls into the base extension method
implicit class FutureApplicativeBind[T, U](lhs: Future[(T) => U]) { 
  def bind(rhs: Future[T]): Future[U] = {
    lhs.ap(rhs)
  }
}
Let's create a new Future lifter to both delay processing & to execute a computation on different thread
This method will not only lifts any type into a Future, but at the same time will allow us to delay a computation by a specified interval after which its processed on a different thread, but without affecting the final composition.

I'm going to use Java's ScheduledExecutorService to tap into some simple threading.
PHP:
// Need to add this import at the top of our code
import java.util.concurrent._

// Wrapper method to simplify the use of [B]ScheduledExecutorService[/B]
def scheduleAfter[T](call: Callable[T], delay: Long, unit: TimeUnit) = {
  val pool = Executors.newScheduledThreadPool(1)
  pool.schedule(call, delay, unit)
  pool.shutdown()
}

// Our new Future lifter method, that can lift any type, and run a computation after defined interval
// Our default interval is 1 second. 
def delayed[T](e: T, delay: Long = 1L, unit: TimeUnit = TimeUnit.SECONDS): Future[T] = {
  Future[T]({ f => 
    println(s"Delaying Future for ${e}")
    val call = new Callable[Unit]() {
      def call = {
        println(s"Completed Future for ${e}")
        f(e)
      }
    }
    scheduleAfter(call, delay, unit)
  })
}
delayed method is essentially the same as the pureFuture lifter, except that we now have code included for running this computation on a separate thread, after a defined delay.
PHP:
def pureFuture[T](v: T): Future[T] = { 
  Future[T]({ f => f(v) })
}
Note:
[table="width: 100%, class: outer_border"]
[tr]
[td]The println statements are included simply for effect i.e. so we can visually see in what sequence things are executed under the covers.[/td]
[/tr]
[/table]

Let see this in use:
PHP:
def add(lhs: Int, rhs: Int): Int = lhs + rhs

pureFuture((add _).curried)
  .bind(delayed(2)) 
  .bind(delayed(3))
  .map(v => v * 9)
  .onResult(f => println(f))
The output for this is as follows:
Code:
Delaying Future for 2
Completed Future for 2
Delaying Future for 3
Completed Future for 3
45
As you can the first delayed(2) is delayed and computed even before the second delayed starts i.e. the computation although using threads is not concurrent. Why?
 
Last edited:

[)roi(]

Executive Member
Joined
Apr 15, 2005
Messages
5,579
#37
Future concurrency problem
The reason why our delayed lifter does not support concurrency stems directly from our choice to use flatMap in the Future's applicative method because as we confirmed with the Either type; the flatMap (monad) operation is algebraic strictly sequential. So to fix this we have to remove flatMap and replace it with something that enables concurrency.

To fix this we're going to use some Tuple "magic"
Let's review firstly what a Tuple is?
As I detailed in an earlier post;
More importantly this:
The entire sequence of tuple values is treated as a single input set with a finite number of elements;
This knowledge of the elements of a tuple being treated as a single input set; essentially concurrently lends itself to a solution for our Future; and a way around our flatMap (monad) limitation.

So let's construct a method to take 2 applicative operands and spit out a single tuple of these operands:
For example: 2 + 3 (2 is the left hand side operand, and 3 is the right hand side operand); however in our Future example keep in mind that these future values (2, 3) are actually composited with the curried form of add i.e.
PHP:
implicit class FutureZip[T, U](lhs: Future[T]) { 
  def zip(rhs: Future[U]): Future[(T, U)] = {
    Future[(T, U)]({ f => 
      lhs.onResult({ a => if (<? right hand side?>) { f((a, <? right hand side?>)) } })
      rhs.onResult({ b => if (<? left hand side?>) { f((<? left hand side?>, b)) } }) 
    })
  }
}
Above the skeleton for this zipping (tuple conversion process); but we have a problem -- when we we're in onResult closure for the lhs (left hand side) operand we only have access to the value stored inside the lhs Future; but to make a Tuple of the two operands we also need the right hand value.

Oops? In the current form of our Future there is just is no practical way to solve this problem..., well not without changing some internals to allow us access this value.
PHP:
case class Future[T](val f: ((T) => Unit) => Unit) {
  var cache: Option[T] = None
}
Ok, so we went back to out Future case class and added a cache variable of type Option, that is initially set to None, then in the onResult method, we'll add a way to initialise this we the value we need:
PHP:
implicit class FutureOnResultMethod[T](lhs: Future[T]) { 
  def onResult(callback: (T) => Unit): Unit = {
    lhs.f( v => {
      lhs.cache = Some(v)
      callback(v)
    })
  }
}
Finally let's go back to our zip function and fill in the blanks:
PHP:
implicit class FutureZip[T, U](lhs: Future[T]) { 
  def zip(rhs: Future[U]): Future[(T, U)] = {
    Future[(T, U)]({ f => 
      lhs.onResult({ a => if (!rhs.cache.isEmpty) { f((a, rhs.cache.get)) } })
      rhs.onResult({ b => if (!lhs.cache.isEmpty) { f((lhs.cache.get, b)) } }) 
    })
  }
}
...and there we have it, a zip function that creates a Tuple of two Future operands. Only step remaining is to replace the flatMap with this zip function, as follows:
PHP:
implicit class FutureApplicativeMethod[T, U](lhs: Future[(T) => U]) { 
  def ap(rhs: Future[T]): Future[U] = {
    lhs.zip(rhs).map(z => z._1(z._2))
  }
}
FYI in Scala we access the elements inside of Tuple using ._1 for the first element, ._2 for the second element and so on. Considering these elements represent the left and right operands of computation, we can composite them together for a result.

Finally let's re-run our Future add example using the two delayed Future computations:
PHP:
pureFuture((add _).curried)
  .bind(delayed(2)) 
  .bind(delayed(3))
  .map(v => v * 9)
  .onResult(f => println(f))
The output for this is as follows:
Code:
Delaying Future for 2
Delaying Future for 3
Completed Future for 2
Completed Future for 3
45
As you can see the both the delayed Future computations occur first (re the "Delaying Future for...") message; and then the "Completed Future for..." messages follow later. This modification will repeat across as many operands are included in the computation.
i.e. it's proof of not only concurrency, but also provides that our approach secure the integrity of the overall computation; answer is still delivered as 45

.and just to prove that this works equally well with our input validation, here's an example where we create a new account using a composite function of our account initialiser and the input validation, curried and lifted into a Future and then bound with the delayed input values.
PHP:
val createValidAccount = (id: Int, email: String, name: String) => 
  (createAccount 
    <*> Valid.Account.id(id) 
    <*> Valid.Account.email(email) 
    <*> Valid.Account.name(name))

pureFuture(createValidAccount.curried)
  .bind(delayed(1))
  .bind(delayed("jack@nofat.com"))
  .bind(delayed("jack"))
  .onResult(v => println(v))
...and the output from that is;
Code:
Delaying Future for 1
Delaying Future for jack@nofat.com
Delaying Future for jack
Completed Future for 1
Completed Future for jack@nofat.com
Completed Future for jack
Right(Account(1,jack@nofat.com,jack))
Note:
[table="width: 100%, class: outer_border"]
[tr]
[td]We've achieved real concurrent multi-threading by treating these computations as algebraic immutable entities; in this way concurrency almost becomes an after-thought. We certainly never once had to consider using thread locks, or even had to be concerned about data races.[/td]
[/tr]
[/table]

Here's a link to a more in-depth exploration of concurrent multi-threading using applicatives for larger data sets, including an in-depth comparison of this approach versus that typically employed by languages like C++.
https://bartoszmilewski.com/category/multithreading/

*errata*: fixed the link at the end related to both Applicative and C++
 
Last edited:

[)roi(]

Executive Member
Joined
Apr 15, 2005
Messages
5,579
#38
Btw that's the conclusion to this.
Let me know if you have any questions or need help translating this code to your preferred language.
 
Top