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
(f (a -> b), f a) -> f bSeem similar to
(a → b → c) → (a → b) → a → cRe-writing the second using a = f, b = a, and c = b I get
(f -> a -> b) -> (f -> a) -> f -> bPresuming 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.
const S = f => g => x => f(x)(g(x))
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
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