Applicative Functor / SKI combinator calculus

SKI_Applicative.scala

object SKI_Applicative {
/*
First, let's talk about the SK combinator calculus and how it contributes to solving your problem.

The SK combinator calculus is made of two functions (aka combinators): S and K. It is sometimes called the SKI combinator calculus, however, the I combinator can be derived from S and K. The key observation of SK is that it is a turing-complete system and therefore, anything that can be expressed as SK is also turing-complete. Here is a demonstration that Scala's type system is turing-complete (and therefore, undecidable) for example[1].

The K combinator is the most trivial of the two. It is sometimes called "const" (as in Haskell). There is also some discussion about its evaluation strategy in Scala and how to best express it[2]. The K function might be paraphrased as, "takes a value and returns a (constant) unary function that always returns that value."
*/
  def k[A, B]: A => B => A =
    a => _ => a

/*
Onto the S combinator. The S combinator can be paraphrased as "takes two functions and returns a function that applies in a specific manner." I note that the wikipedia page[3] express S as: Sxyz = xz(yz). If that is a little too terse, let me convert that to Scala syntax for you. It's much the same syntax but with the def keyword, some parentheses and type-annotations.
*/
  def s[A, B, C](x: A => B => C, y: A => B): A => C =
    z => x(z)(y(z))

/*
You might notice that the body of S is remarkably similar to the code in your original problem. f1(x, f2(x, b))

How does the S combinator relate to an applicative functor? Well, browse the code below which gives the full interface for an applicative functor starting at a basic functor and then introducing the properties of an applicative functor. That is to say, all applicative functors are functors (says so in the name even!) by imposing further restrictions.
*/
  trait Functor[F[+_]] {
    // lift a unary function
    def fmap[A, B](f: A => B): F[A] => F[B]
  }

  trait Ap[F[+_]] extends Functor[F] {
    // apply a function in an environment (F).
    def ap[A, B](f: F[A => B]): F[A] => F[B]
  }

  trait Applicative[F[+_]] extends Ap[F] {
    def point[A](a: A): F[A]
    override final def fmap[A, B](f: A => B) =
      ap(point(f))
  }

/*
The function most relevant to your problem is the ap function. Notice that it looks like general function application but with a considerable distinction. That is, we could write a function to apply a function. I have seen some Scala libraries do this with some fancy method and calling it "the pipe operator" (which I assume was taken from F#).
*/
  def functionApplication[A, B](f: A => B): A => B =
    f(_)
/*
However, we "lift" that signature into an environment (F) so that (A => B) => A => B becomes F[A => B] => F[A] => F[B]. We could get back to basic functional application by making F a data structure that holds a single value:
*/
  case class Identity[+A](value: A)

  val IdentityApplicative: Applicative[Identity] = new Applicative[Identity] {
    // Back down to general function application.
    def ap[A, B](f: Identity[A => B]) =
      a => Identity(f.value(a.value))
    def point[A](a: A) =
      Identity(a)
  }

/*
However, what about other environments? Let's invent one that is more pertinent to your example. This environment is "a function that accepts an integer." It looks like this:
*/
  case class Inter[+A](apply: Int => A)

/*
And now for its Applicative:
*/

  implicit val InterApplicative: Applicative[Inter] = new Applicative[Inter] {
    // Application in the Inter environment. Note the similarity to the S combinator.
    def ap[A, B](f: Inter[A => B]) =
      a => Inter(n => f.apply(n)(a.apply(n)))
    def point[A](a: A) =
      Inter(_ => a)
  }

/*
Here we have provided a new Applicative instance for yet another environment. The InterApplicative#ap method is remarkable similar to the S combinator above. That's because it is in fact the same.

Now, if we had some code, such as x => f.apply(x, g.apply(x)), then the InterApplicative would be a bit clumsy to use. So, we could do some pimping to make it a lot easier:
*/
  trait Applicativeness[F[+_], A, B] {
    val q: F[A => B]
    // We can provide a handy method for performing application in any applicative functor.
    def <*>(r: F[A])(implicit A: Ap[F]): F[B] =
      A.ap(q)(r)
  }

/*
Next we need some implicits to get where we need to go.
*/
  implicit def ApplicativenessValue[F[+_], A, B](x: F[A => B]): Applicativeness[F, A, B] = new Applicativeness[F, A, B] {
    val q = x
  }

/*
So now we might have a use-case like so:
*/
  object UseCase1 {
    val f: Inter[String => List[String]] =
      Inter(n => s => List.fill(n)(s))
    val g: Inter[String] =
      Inter(_.toString.reverse)

/*
Then we might use it like so:
*/
    def use(x: Int): List[String] =
      f.apply(x)(g.apply(x))

/*
Now your objection here is the application to x occurring twice. I agree it is clumsy. It would be *even worse* to introduce language syntax for this case. Let's not do that.

Notice that we have pretty much repeated the body of the InterApplicative#ap method. We should just use it. Even better, we could use our nice handy syntax.
*/
    def useAgain =
      f <*> g
  }

/*
And so there we have it. We have eschewed the clumsy application to the free variable by exploiting the S combinator, which has been implemented more generally as an applicative functor. In particular, our <*> is availabe to use for *any* applicative functor, not just Inter or Identity -- there are *zillions* of these in every-day programming.

As it happens, this subject gets a fair amount of exposure in Functional Programming in Scala[4], with exercises leading up to this point and also going beyond.

Hope that helps. Remember, libraries, lots and lots of libraries, not language syntax -- more flexible, neater and no cost to the language -- why would you do anything else?
*/
}

/*
[1] http://apocalisp.wordpress.com/2011/01/13/simple-ski-combinator-calculus-in-scalas-type-system/
[2] http://apocalisp.wordpress.com/2010/04/21/a-proper-constant-function-in-scala/
[3] http://en.wikipedia.org/wiki/SKI_combinator_calculus
[4] http://www.manning.com/bjarnason/
*/