Const implementation without Fully Qualified Type Representatives

[Avaq]

During a recent conversation between @davidchambers and I, we came up with a way to define an Applicative Const Functor that can be used to implement Lenses, without needing a Monoid up front. The conversation is starting to escape my memory, so I'll just put the idea down here lest we forget.

The Problem

As I understand, the need for a Monoid on Const currently blocks progress on this library. In particular, there currently is no way to implement Fantasy Land's Applicative for Const in the way Haskell does:

data Const a b = Const {getConst :: a}

instance Monoid m => Applicative (Const m) where
    pure _ = Const mempty
    (<*>) = coerce (mappend :: m -> m -> m)

Here we see Applicative implemented for Const m by restricting to ms that have Monoid, and just putting mempty as the actual context-value of the Const. Haskell then relies on the type system to make it so when getConst is resolved, it gets a value of the correct specific Monoid.

In JavaScript (and specifically, Fantasy Land as it is right now), we don't have a way to carry type information along with our Const instances so that when getConst is used, we can put a value of the correct Monoid there:

Const['fantasy-land/of'] = function(_){
  return new Const(/* What do I put here?! */)
}

Solutions

• One proposed solution is to update Fantasy Land to allow it to actually carry that type information: proposal: fully-qualified type representatives fantasyland/fantasy-land#315. This approach will take a lot of work, followed by months or years of propagation through the community.
• Another solution is the one taken in the Initial Pull Request: Users have to supply a Monoid type representative to obtain specialized Const type representatives. The downside here is in the ergonomics.

---

An alternative that I came up with is to have a binary type implementation for Const, where reliance on the type system is removed, and the fallback value is provided by the user when evaluating the Const:

import {tagged} from 'daggy';

const Constant = tagged('Const', {
  Const: ['context'],
  NoConst: [],
});

// We can implement pure by simply returning NoConst:
Constant['fantasy-land/of'] = function(_){
  return Constant.NoConst;
};

Constant.prototype['fantasy-land/map'] = function(_){
  return this;
};

Constant.prototype['fantasy-land/ap'] = function(other){
  return other.cata({
    NoConst: () => this,
    Const: otherContext => this.cata({
      NoConst: () => other,
      Const: context => Constant.Const (otherContext['fantasy-land/concat'](context))
    })
  });
};

// The provision of a Monoid is moved all the way to the evaluation step:
const getConst = monoidRepr => c => c.cata({
  NoConst: () => monoidRepr['fantasy-land/empty'](),
  Const: context => context
});

A few observations:

• Const itself is almost Monoidal here, were it not for the other type param (NoConst ++ Const a = Const a, etc)
• It's the classic layer of indirection: represent your effects instead of embedding them, and run them during interpretation

---

What do you think? Does this approach have any benefits over the one taken in #1 ?

/cc @masaeedu

[Avaq]

I think ap could also be implemented on top of getConst, like:

Constant.prototype['fantasy-land/ap'] = function(other){
  return other.cata({
    NoConst: () => this,
    Const: otherContext => Constant.Const (
      otherContext['fantasy-land/concat'] (getConst (otherContext.constructor) (this))
    )
  });
};

[Avaq]

We can even make the Applicative implementation conditional, like done in other types to get better type introspection:

//...
function Const(x){
  const cnst = Object.create (Const$prototype);
  if(Monoid.test(x)){
    cnst['fantasy-land/ap'] = Const$prototype$ap;
  }
}
//...

Applicative.test (Const ("_")) // true
Applicative.test (Const (42)) // false
Applicative.test (NoConst) // true

[Avaq]

Ah. I just remembered another idea David and I had: Since Lenses don't actually use the Applicative instance on Const, we could export two Const types from this library: One that just has Functor, and doesn't need a Monoid typeRep when evaluated. This one could be used for lens implementations. And the other being the Applicative Functor variant proposed above.

[masaeedu]

Hello @Avaq. I think this is a pretty good idea. It's worth noting that any Apply is susceptible to this trick. So in Haskell, you can write:

data AddPure f a = Pure a | Impure (f a)

instance Apply f => Applicative (AddPure f)
  where
  pure = Pure
  
  Pure ab <*> Pure a = Pure $ ab a
  Pure ab <*> Impure fa = Impure $ ab <$> fa
  Impure fab <*> Pure a = Impure $ (\ab -> ab a) <$> fab
  Impure fab <*> Impure fa = Impure $ fab <.> fa

interpret :: Apply f => (forall x. x -> f x) -> AddPure f a -> f a
interpret pure (Pure a) = pure a
interpret _ (Impure fa) = fa

All this to say the approach you've outlined definitely works and gives a lawful Applicative. It's possible that a general purpose utility for "deferring" the pure implementation of Applys would be useful, although I can't immediately see a use for it beyond Const.

[Avaq]

Thanks for your thoughts @masaeedu!

It's possible that a general purpose utility for "deferring" the pure implementation of Applys would be useful, although I can't immediately see a use for it beyond Const.

My inclination would be to go with the const-specific approach initially, and extract out if we find ourselves duplicating the approach.