Join us now. It is free, and it takes less than 1 minute to register.
Register now
Subscribe to our daily newsletter. It is free, and it comes with many benefits.


+ Reply to Thread
Page 3 of 3 FirstFirst 123
Results 31 to 41 of 41

Thread: Another Functional Programming Challenge

  1. #31
    Super Grandmaster
    Join Date
    Apr 2005
    Location
    Posts
    5,444
    Mentioned
    2 Post(s)
    Tagged
    0 Thread(s)

    Default

    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 Code:
    implicit class EitherApplicativeMethod[ETU](lhsEither[List[E], (T) => U]) { 
      
    def ap(rhsEither[List[E], T]): Either[List[E], U] = {
        (
    lhsrhsmatch {
          case (
    Right(success), _) => rhs.map(success)
          case (
    Left(fail), Right(_)) => Left(fail)
          case (
    Left(fail1), Left(fail2)) => Left(fail1 ::: fail2)
        }
      }
    }

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


    def validate(emailString): 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 Code:
    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 by [)roi(]; 14-04-2018 at 11:21 PM.
    absurd :: Void → a ≝ id ⋅Void → q

  2. #32
    Super Grandmaster
    Join Date
    Apr 2005
    Location
    Posts
    5,444
    Mentioned
    2 Post(s)
    Tagged
    0 Thread(s)

    Default

    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 Code:
      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 Code:
      (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 by [)roi(]; 15-04-2018 at 10:06 PM.
    absurd :: Void → a ≝ id ⋅Void → q

  3. #33
    Super Grandmaster
    Join Date
    Apr 2005
    Location
    Posts
    5,444
    Mentioned
    2 Post(s)
    Tagged
    0 Thread(s)

    Default

    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 Code:
    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:
    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.

    Ok so let's define our lifter function
    To lift a value and/or computation into our Future type.
    PHP Code:
    def pureFuture[T](vT): Future[T] = { 
      
    Future[T]({ => 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 Code:
    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 Code:
    implicit class FutureOnResultMethod[T](lhsFuture[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 Code:
    pureFuture(1)
      .
    onResult(=> println(v)) // 1 
    Now let's make our Future a functor (i.e. add the map method)
    PHP Code:
    implicit class FutureFunctorMethod[T](lhsFuture[T]) { 
      
    def map[U](g: (T) => U): Future[U] = {
        
    Future[U]({ => lhs.onResult({ => 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 Code:
    pureFuture(1)
      .
    map(=> 1)
      .
    onResult(=> println(v)) // 2 
    Now let's make our Future a monad (i.e. add the flatMap method)
    PHP Code:
    implicit class FutureMonadMethod[T](lhsFuture[T]) { 
      
    def flatMap[U](g: (T) => Future[U]): Future[U] = {
        
    Future[U]({ => lhs.onResult({ => 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[U]), and because the result is Future[U], 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 Code:
    pureFuture(3)
      .
    map(=> 4)
      .
    flatMap(=> pureFuture(if(== 0"even" else "odd"))
      .
    onResult(=> 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 by [)roi(]; 16-04-2018 at 06:00 PM.
    absurd :: Void → a ≝ id ⋅Void → q

  4. #34
    Super Grandmaster
    Join Date
    Apr 2005
    Location
    Posts
    5,444
    Mentioned
    2 Post(s)
    Tagged
    0 Thread(s)

    Default

    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 Code:
    implicit class FutureApplicativeMethod[TU](lhsFuture[(T) => U]) { 
      
    def ap(rhsFuture[T]): Future[U] = {
        
    lhs.flatMap(=> rhs.map(f))
      }
    }

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

    implicit class FutureApplicativeBind[TU](lhsFuture[(T) => U]) { 
      
    def bind(rhsFuture[T]): Future[U] = {
        
    lhs.ap(rhs)
      }

    This allows use to write the following code:
    PHP Code:
    pureFuture((add _).curried)
      .
    ap(pureFuture(2))
      .
    ap(pureFuture(3))
      .
    onResult(=> println(f)) // 5

    (pureFuture((add _).curried
      <*> 
    pureFuture(2
      <*> 
    pureFuture(3))
      .
    map(=> 9)
      .
    onResult(=> println(f)) // 45 
    Challenge:
    Can you get our Either input validation shown below to work with our new Future type?
    PHP Code:
    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 
    absurd :: Void → a ≝ id ⋅Void → q

  5. #35
    Super Grandmaster
    Join Date
    Apr 2005
    Location
    Posts
    5,444
    Mentioned
    2 Post(s)
    Tagged
    0 Thread(s)

    Default

    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 Code:
    pureFuture(createAccount 
      
    <*> Valid.Account.id(-1
      <*> 
    Valid.Account.email("jackienolean.com"
      <*> 
    Valid.Account.name("Jackie"))
      .
    onResult(=> println(v)) // Left(List(Invalid ID, Invalid EMAIL))

    // Alternative simplify the Either Account validation applicative by compositing it into a new function
    val createValidAccount = (idIntemailStringnameString) => 
      (
    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"[email protected]""jack"))
      .
    onResult(=> println(v)) // Right(Account(1,[email protected],jack)) 
    Lifting our Either createAccount Either Applicative into a Future and then mapping over the validations
    PHP Code:
    // Method chaining is used in conjunction with Futures map method to validate input
    pureFuture(createAccount)
      .
    map(=> e.bind(Valid.Account.id(-1)))
      .
    map(=> e.bind(Valid.Account.email("[email protected]")))
      .
    map(=> e.bind(Valid.Account.name("Jac")))
      .
    onResult(=> println(v)) // Left(List(Invalid ID, Invalid NAME))

    // Operator composition is used in conjunction with Futures map method to validate input
    pureFuture(createAccount)
      .
    map(=> <*> Valid.Account.id(-1))
      .
    map(=> <*> Valid.Account.email("[email protected]"))
      .
    map(=> <*> Valid.Account.name("Jackie"))
      .
    onResult(=> println(v)) // Left(List(Invalid ID)) 
    absurd :: Void → a ≝ id ⋅Void → q

  6. #36
    Super Grandmaster
    Join Date
    Apr 2005
    Location
    Posts
    5,444
    Mentioned
    2 Post(s)
    Tagged
    0 Thread(s)

    Default

    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 Code:
    // our base method extension; Note: that the internal computation is still monadic i.e. it uses flatMap
    implicit class FutureApplicativeMethod[TU](lhsFuture[(T) => U]) { 
      
    def ap(rhsFuture[T]): Future[U] = {
        
    lhs.flatMap(=> rhs.map(f))
      }
    }

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

    //alternative API, calls into the base extension method
    implicit class FutureApplicativeBind[TU](lhsFuture[(T) => U]) { 
      
    def bind(rhsFuture[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 Code:
    // 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], delayLongunitTimeUnit) = {
      
    val pool Executors.newScheduledThreadPool(1)
      
    pool.schedule(calldelayunit)
      
    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](eTdelayLong 1LunitTimeUnit TimeUnit.SECONDS): Future[T] = {
      
    Future[T]({ => 
        
    println(s"Delaying Future for ${e}")
        
    val call = new Callable[Unit]() {
          
    def call = {
            
    println(s"Completed Future for ${e}")
            
    f(e)
          }
        }
        
    scheduleAfter(calldelayunit)
      })

    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 Code:
    def pureFuture[T](vT): Future[T] = { 
      
    Future[T]({ => f(v) })

    Note:
    The println statements are included simply for effect i.e. so we can visually see in what sequence things are executed under the covers.

    Let see this in use:
    PHP Code:
    def add(lhsIntrhsInt): Int lhs rhs

    pureFuture
    ((add _).curried)
      .
    bind(delayed(2)) 
      .
    bind(delayed(3))
      .
    map(=> 9)
      .
    onResult(=> 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 by [)roi(]; 19-04-2018 at 10:24 PM.
    absurd :: Void → a ≝ id ⋅Void → q

  7. #37
    Super Grandmaster
    Join Date
    Apr 2005
    Location
    Posts
    5,444
    Mentioned
    2 Post(s)
    Tagged
    0 Thread(s)

    Default

    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 Code:
    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 Code:
    case class Future[T](val f: ((T) => Unit) => Unit) {
      var 
    cacheOption[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 Code:
    implicit class FutureOnResultMethod[T](lhsFuture[T]) { 
      
    def onResult(callback: (T) => Unit): Unit = {
        
    lhs.f=> {
          
    lhs.cache Some(v)
          
    callback(v)
        })
      }

    Finally let's go back to our zip function and fill in the blanks:
    PHP Code:
    implicit class FutureZip[TU](lhsFuture[T]) { 
      
    def zip(rhsFuture[U]): Future[(TU)] = {
        
    Future[(TU)]({ => 
          
    lhs.onResult({ => if (!rhs.cache.isEmpty) { f((arhs.cache.get)) } })
          
    rhs.onResult({ => if (!lhs.cache.isEmpty) { f((lhs.cache.getb)) } }) 
        })
      }

    ...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 Code:
    implicit class FutureApplicativeMethod[TU](lhsFuture[(T) => U]) { 
      
    def ap(rhsFuture[T]): Future[U] = {
        
    lhs.zip(rhs).map(=> 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 Code:
    pureFuture((add _).curried)
      .
    bind(delayed(2)) 
      .
    bind(delayed(3))
      .
    map(=> 9)
      .
    onResult(=> 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 Code:
    val createValidAccount = (idIntemailStringnameString) => 
      (
    createAccount 
        
    <*> Valid.Account.id(id
        <*> 
    Valid.Account.email(email
        <*> 
    Valid.Account.name(name))

    pureFuture(createValidAccount.curried)
      .
    bind(delayed(1))
      .
    bind(delayed("[email protected]"))
      .
    bind(delayed("jack"))
      .
    onResult(=> println(v)) 
    ...and the output from that is;
    Code:
    Delaying Future for 1
    Delaying Future for [email protected]
    Delaying Future for jack
    Completed Future for 1
    Completed Future for [email protected]
    Completed Future for jack
    Right(Account(1,[email protected],jack))
    Note:
    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.

    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 by [)roi(]; 18-04-2018 at 01:33 PM.
    absurd :: Void → a ≝ id ⋅Void → q

  8. #38
    Super Grandmaster
    Join Date
    Apr 2005
    Location
    Posts
    5,444
    Mentioned
    2 Post(s)
    Tagged
    0 Thread(s)

    Default

    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.
    absurd :: Void → a ≝ id ⋅Void → q

  9. #39
    Grandmaster
    Join Date
    Oct 2005
    Posts
    2,442
    Mentioned
    1 Post(s)
    Tagged
    0 Thread(s)

    Default

    Out of office for 3 days, but will definitely catchup on this. Thanks for all your effort

  10. #40
    Super Grandmaster
    Join Date
    Apr 2005
    Location
    Posts
    5,444
    Mentioned
    2 Post(s)
    Tagged
    0 Thread(s)

    Default

    Quote Originally Posted by _kabal_ View Post
    Out of office for 3 days, but will definitely catchup on this. Thanks for all your effort
    Only a pleasure -- hopefully you'll find some inspiration in amongst all of this.
    absurd :: Void → a ≝ id ⋅Void → q

  11. #41
    Super Grandmaster
    Join Date
    Apr 2005
    Location
    Posts
    5,444
    Mentioned
    2 Post(s)
    Tagged
    0 Thread(s)

    Default

    Ideas for the next functional thread:
    First challenge / topic was beginner's friendly; whereas this one broached the space between intermediate to advanced; largely because it was not just about learning technique but rather on acquiring knowledge by constructing a few functional types.

    Next Challenge
    For any other interested parties I'm looking to kick off another more beginner's centric functional thread -- problem is always trying to find a good "problem to centre this challenge around" -- so if anybody had some ideas then please let me know via PM.
    absurd :: Void → a ≝ id ⋅Void → q

+ Reply to Thread
Page 3 of 3 FirstFirst 123

Similar Threads

  1. Functional Programming
    By [)roi(] in forum Software and Web Development
    Replies: 67
    Last Post: 20-11-2016, 03:21 PM
  2. Functional Programming List
    By [)roi(] in forum Software and Web Development
    Replies: 6
    Last Post: 13-11-2016, 02:38 PM
  3. Functional Programming Concept Game
    By [)roi(] in forum Software and Web Development
    Replies: 7
    Last Post: 21-08-2016, 11:01 PM
  4. SA school kids take on robot programming challenge
    By Kevin Lancaster in forum Broadband and IT News
    Replies: 0
    Last Post: 20-07-2015, 05:32 PM
  5. SA coders can win R100,000 in programming challenge
    By QuintonB in forum Broadband and IT News
    Replies: 10
    Last Post: 31-07-2012, 08:34 AM

Bookmarks

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •