How come I can pass functions to a lifted R.divide?

Question

Given the following:

var average = R.lift(R.divide)(R.sum, R.length)

How come this works as a pointfree implementation of average? I don't understand why I can pass R.sum and R.length when they are functions and therefore, I cannot map the lifted R.divide over the functions R.sum and R.length unlike in the following example:

var sum3 = R.curry(function(a, b, c) {return a + b + c;});
R.lift(sum3)(xs)(ys)(zs)

In the above case the values in xs, ys and zs are summed in a non deterministic context, in which case the lifted function is applied to the values in the given computational context.

Expounding further, I understand that applying a lifted function is like using R.ap consecutively to each argument. Both lines evaluate to the same output:

R.ap(R.ap(R.ap([tern], [1, 2, 3]), [2, 4, 6]), [3, 6, 8])
R.lift(tern)([1, 2, 3], [2, 4, 6], [3, 6, 8])

Checking the documentation it says:

"lifts" a function of arity > 1 so that it may "map over" a list, Function or other object that satisfies the FantasyLand Apply spec.

And that doesn't seem like a very useful description at least for me. I'm trying to build an intuition regarding the usage of lift. I hope someone can provide that.

Alisander

Answer 1

The first cool thing is that a -> b can support map. Yes, functions are functors!

Let's consider the type of map:

map :: Functor f => (b -> c) -> f b -> f c

Let's replace Functor f => f with Array to give us a concrete type:

map :: (b -> c) -> Array b -> Array c

Let's replace Functor f => f with Maybe this time:

map :: (b -> c) -> Maybe b -> Maybe c

The correlation is clear. Let's replace Functor f => f with Either a, to test a binary type:

map :: (b -> c) -> Either a b -> Either a c

We often represent the type of a function from a to b as a -> b, but that's really just sugar for Function a b. Let's use the long form and replace Either in the signature above with Function:

map :: (b -> c) -> Function a b -> Function a c

So, mapping over a function gives us a function which will apply the b -> c function to the original function's return value. We could rewrite the signature using the a -> b sugar:

map :: (b -> c) -> (a -> b) -> (a -> c)

Notice anything? What is the type of compose?

compose :: (b -> c) -> (a -> b) -> a -> c

So compose is just map specialized to the Function type!

The second cool thing is that a -> b can support ap. Functions are also applicative functors! These are known as Applys in the Fantasy Land spec.

Let's consider the type of ap:

ap :: Apply f => f (b -> c) -> f b -> f c

Let's replace Apply f => f with Array:

ap :: Array (b -> c) -> Array b -> Array c

Now, with Either a:

ap :: Either a (b -> c) -> Either a b -> Either a c

Now, with Function a:

ap :: Function a (b -> c) -> Function a b -> Function a c

What is Function a (b -> c)? It's a bit confusing because we're mixing the two styles, but it's a function that takes a value of type a and returns a function from b to c. Let's rewrite using the a -> b style:

ap :: (a -> b -> c) -> (a -> b) -> (a -> c)

Any type which supports map and ap can be "lifted". Let's take a look at lift2:

lift2 :: Apply f => (b -> c -> d) -> f b -> f c -> f d

Remember that Function a satisfies the requirements of Apply, so we can replace Apply f => f with Function a:

lift2 :: (b -> c -> d) -> Function a b -> Function a c -> Function a d

Which is more clearly written:

lift2 :: (b -> c -> d) -> (a -> b) -> (a -> c) -> (a -> d)

Let's revisit your initial expression:

//    average :: Number -> Number
const average = lift2(divide, sum, length);

What does average([6, 7, 8]) do? The a ([6, 7, 8]) is given to the a -> b function (sum), producing a b (21). The a is also given to the a -> c function (length), producing a c (3). Now that we have a b and a c we can feed them to the b -> c -> d function (divide) to produce a d (7), which is the final result.

So, because the Function type can support map and ap, we get converge at no cost (via lift, lift2, and lift3). I'd actually like to remove converge from Ramda as it isn't necessary.

---

Note that I intentionally avoided using R.lift in this answer. It has a meaningless type signature and complex implementation due to the decision to support functions of any arity. Sanctuary's arity-specific lifting functions, on the other hand, have clear type signatures and trivial implementations.

Exfoliate

Very nice! I'd love to see this answer lifted into a blog post! – Nagana

When (b -> c -> d) -> (a -> b) -> (a -> c) -> (a -> d) is implemented as a combinator it looks like bird = f => g => h => x => f(g(x)) (h(x)). It looks similar to psi = f => g => x => y => f(g(x)) (g(y)). I wonder how the name of this bird is? – Flaminius

To answer my own question: It's the starling', which is the composition of applicative's ap on functions const ap = f => g => x => f(x) (g(x)) and composition const comp = f => g => x => f(g(x)): const starling_ = comp(comp(ap)) (comp). – Flaminius

Answer 2

As I have hard time understanding the same issue, I decided to take a peek from Ramda's source code. Will write a blogpost about this in the future. Meanwhile—I made a commented gist how Ramda's lift work step by step.

from: https://gist.github.com/philipyoungg/a0ab1efff1a9a4e486802a8fb0145d9e

// Let's make an example function that takes an object and return itself.
// 1. Ramda's lift level
lift(zipObj)(keys, values)({a: 1}) // returns {a: 1}

// this is how lift works in the background
module.exports = _curry2(function liftN(arity, fn) {
  var lifted = curryN(arity, fn);
  return curryN(arity, function() {
    return _reduce(ap, map(lifted, arguments[0]), Array.prototype.slice.call(arguments, 1)); // found it. let's convert no 1 to no 2
  });
});

// 2. Ramda's reduce level
reduce(ap, map(zipObj, keys))([values])
// first argument is the function, second argument is initial value, and the last one is lists of arguments. If you don't understand how reduce works, there's a plenty of resources on the internet

// 3. Ramda's ap level
ap(map(zipObj, keys), values)

// how ap works in the background
module.exports = _curry2(function ap(applicative, fn) {
  return (
    typeof applicative.ap === 'function' ?
      applicative.ap(fn) :
    typeof applicative === 'function' ? // 
      function(x) { return applicative(x)(fn(x)); } : // because the first argument is a function, ap return this.
    // else
      _reduce(function(acc, f) { return _concat(acc, map(f, fn)); }, [], applicative)
  );
});

// 4. Voilà. Here's the final result.
map(zipObj, keys)({a: 1})(values({a: 1}))

// Hope it helps you and everyone else!

Flocculate