Confusion in understanding Substitution / `ap` type signature and different implementations (functional programming)

Question

I am a student of functional programming, sorry if my question sounds weird--I am trying to wrap my mind around the given type signatures for functions and how they are implemented.

Looking at the signature for ap (Substitution)

https://gist.github.com/Avaq/1f0636ec5c8d6aed2e45

(a → b → c) → (a → b) → a → c

Is given here as

const S = f => g => x => f(x)(g(x));

Which I think I understand. f is a function that takes two parameters, a and b and returns c. g is a function that takes a and returns b. So g(a) returns b and therefore f(a)(b) can be written as f(a)(g(a)), which returns c.

g(a) is the substitute for b ?

Ok now I'm looking at a different implementation that still makes sense:

https://github.com/sanctuary-js/sanctuary-type-classes/tree/v7.1.1#ap--applyf--fa-bfa---fb

ap(Identity(Math.sqrt), Identity(64))

The type signature

1. (f (a -> b), f a) -> f b

Seem similar to

2. (a → b → c) → (a → b) → a → c

Re-writing the second using a = f, b = a, and c = b I get

3. (f -> a -> b) -> (f -> a) -> f -> b

Presuming that ap takes two parameters, where in the first f could be some functor that contains a function a -> b and in the second f some functor that contains a returning a functor that substitutes the first functor's function with the end point b given then functor containing a.

Okay, stepping back, these two things looks vastly different and I can't wrap my mind around how they are somehow saying the same thing.

1. const S = f => g => x => f(x)(g(x))

2. ap(Identity(Math.sqrt), Identity(64))

From my understanding, ap(F(g),F(a)) can be express as F(a).map(g) which, again, I still have a hard time equating to const S = f => g => x => f(x)(g(x)). Perhaps I'm misunderstanding something.

...maybe my misunderstanding has to do with the expression of ap and how that correlates to f => g => x => f(x)(g(x)) because I can see how they both express the same signature but I don't see them as the same thing.

Anyone who can lend some cognitive assistance here, I would greatly appreciate it

Answer 1

ap is the name for a transformation that behaves the same way on a large number of container types known as Applicative Functors. One such container type is the Function: it can be treated as a container of its return value.

The S combinator you found in my gist comes from the untyped Lambda Calculus and is a transformation of a Function specifically. It happens to also be a valid implementation of Applicative Functor for Function, and it happens to be the implementation of choice for both Ramda and Sanctuary. This is why you can use ap as S.

To gain an understanding of how ap is S, let's have a look at the signature for ap:

Apply f => (f (a -> b), f a) -> f b

And let's get rid of the comma by currying the function. This should make the next steps a little easier to follow:

Apply f => f (a -> b) -> f a -> f b

The Apply f part shows that, where ever we see f a, we can use an Applicative Functor container that contains a. Let's specialise this signature for the Function container, by replacing f with (Function x). x is the input to the function, and what follows is the output.

(Function x) (a -> b) -> (Function x) a -> (Function x) b

This reads as: Given a Function from x to a Function from a to b, and a Function from x to a, returns a Function from x to b.

We can remove the brackets around Function x, because of the way constructor associativity works:

Function x (a -> b) -> Function x a -> Function x b

And another way to write Function a b is using the arrow notation: (a -> b), so in the next step we do just that:

(x -> (a -> b)) -> (x -> a) -> (x -> b)

And finally we can get rid of the additional brackets again, and find that it's our S combinator:

(x -> a -> b) -> (x -> a) -> x -> b
(a -> b -> c) -> (a -> b) -> a -> c

Answer 2

First of all, I think there is no easy explanation of why the applicative functor for the function type in untyped lambda calculus is called substitution. AFAIK, Schönfinkel originally called this combinator fusing or amalgamation function.

In order to specialize the general applicative functor type (f (a -> b), f a) -> f b (uncurried form), we need to know what the parameterized type variable f exactly represents in the context of the function type.

As every functor applicative functors are parameterized over a single type. The function type constructor, however, needs two types - one for the argument and another for the return value. For functions to be an instance of (applicative) functors, we must therefore ignore the type of the return value. Consequently, f represents (a -> ), ie. the function type itself and the type of its argument. The correct notation for the partially applied function type constructor is actually prefix (->) a, so let's stick to this.

Next, I'm gonna rewrite the general applicative type in curried form and substitute f with (->) r. I use another letter to delimit the type parameter of the applicative from other type variables:

(f (a -> b), f a) -> f b
f (a -> b) -> f a -> f b // curried form

// substitution
(->) r (a -> b) -> (->) r a -> (->) r b // prefix notation
(r -> a -> b) -> (r -> a) -> (r -> b) // infix notation

// omit unnecessary parenthesis
(r -> a -> b) -> (r -> a) -> r -> b

This is exactly the type of the S combinator.