Generalize functors to restricted functors

[masaeedu]

Functor is currently described as:

map :: Functor f => f a ~> (a -> b) -> f b

The fact that there's no constraints on a or b means this is a functor over the category of all types in JS: it maps a morphism between any two types a -> b to a morphism f a -> f b (and implicitly, any type a to the type f a).

In some cases, a type may exhibit the characteristics of being a legal functor over some universe of types, but not behave as a legal functor over every conceivable type.

For example, Promise#then can be used to form a legal functor over non-"thenable" types, and those types only. Consider the following implementation:

const map = f => x => x.then(f)

map(x => x * 2)(Promise.resolve(10)) // Behaves as legal functor, produces Promise containing 20

map(x => ({ then: () => x * 2 }))(Promise.resolve(10)) // Does not behave as legal functor

While Promise does not form a legal functor over morphisms between all types, as shown above, it certainly does form a functor over types that satisfy a constraint (in this case, x => !isThenable(x)).

If the Fantasy Land spec allowed formalization of "functor over the category of some types", many more types naturally occurring in JS could be instantiated as lawful functors/applicatives/monads and benefit from code that works with these abstract classes.

RFunctor could hypothetically look something like this:

class RFunctor (s :: * -> Constraint) f where
  rmap :: (s a, s b) => f a ~> (a -> b) -> f b

instance RFunctor NonThenable Promise where ...

The existing Functor class would simply be RFunctor for a choice of constraint that accepts all types.

The specification has a choice between simply making the behavior of rmap with respect to non-suitable morphisms undefined, or requiring implementers to provide a suitable :: a -> Boolean implementation which will be used to produce type errors for invalid morphisms.

Prior art:

• https://hackage.haskell.org/package/rmonad.
• https://hsenag.livejournal.com/11803.html

Not sure if @hsenag is active on here, but maybe he has some thoughts.

[i-am-tom]

I'm afraid I'm gonna have to give this a 👎 simply because it contains the word "functor". We don't have constraints (let alone constraint kinds) in JS, and I think this opens us up to a lot of misinterpretation. For example, Promise isn't a functor, and it's something I have to explain fairly regularly - I think saying "it's an rfunctor" implies that rfunctor is somehow related to functor, which (in JS) it isn't.

I see where you're coming from, but I'm already worried when we start talking about promises or sets as "lawful functors/applicatives/monads", because they're simply not - as soon as you introduce constraints, you un-introduce "functor" :(

[masaeedu]

@i-am-tom It depends on what you're talking about when you refer to the overloaded term "functor". If you're talking about the category theoretic definition of a functor, it is indeed a valid functor over a restricted subcategory of all possible types. When Haskell users say "functor", they are using a colloquial shortening of "functor over the category of all Haskell types". This is not the only conceivable functor in the world if you're familiar with the underlying mathematical definition.

[masaeedu]

I'm afraid I'm gonna have to give this a 👎 simply because it contains the word "functor"

All that said, if the objection here is only to the naming, I'd be happy with any synonym you can think of to express the concept of functor over a subcategory of all types.

[hsenag]

Just a brief comment for now - I remember trying to write an RFunctor in rmonad, and deciding it was too complicated/ugly. I can't remember the details but I think the constraints got quite hard to manage in practice.

[masaeedu]

@i-am-tom Ok, so here's a hypothetical RFunctor instance for Promises:

const Fn = (() => {
  const id = x => x
  const compose = f => g => a => f(g(a))
  const pipe = fs => fs.reduce((g, f) => a => f(g(a)))

  return { id, compose, pipe }
})()

const Prm = (() => {
  // Misc
  const equals = p1 => p2 => p1.then(x => p2.then(y => Promise.resolve(x === y)))
  const isThenable = a => typeof a.then === "function"

  // RFunctor
  // Promise is a functor over non-thenable types
  const suitable = a => !isThenable(a)
  const rmap = f => p => p.then(f)

  return { equals, isThenable, suitable, rmap }
})()

const Err = (() => {
  // fail :: Error -> ⊥
  const fail = e => { throw e }

  // ensure :: Error -> (a -> Boolean) -> a -> a | ⊥
  const ensure = e => f => a => f(a) ? a : fail(e)

  return { fail, ensure }
})()

const asFunctor = ({ suitable, rmap }) => {
  const err = new TypeError("Unsuitable value")
  const ensureSuitability = Err.ensure(err)(suitable)

  const map = f => rmap(Fn.pipe([ensureSuitability, f, ensureSuitability]))

  return { map }
}

// The instance whose lawfulness is in question
const { map } = asFunctor(Prm)

const test = async () => {  
  // Identity law
  // fmap id = id
  {
    const p = ... // for any promise

    await Prm.equals(p)(map(Fn.id)(p)) || Err.fail("Identity law violated")
  }

  // Composition law
  // fmap (g . f) = fmap g . fmap f
  {
    const { f, g } = ... // for any two morphisms
    const p = ... // and any promise (extensional equality)

    const p1 = map(Fn.compose(f)(g))(p)
    const p2 = Fn.compose(map(f))(map(g))(p)
    await Prm.equals(p1)(p2) || Err.fail("Composition law violated")
  }
}

test().then(_ => console.log("success!"))

I can't really formally prove that the map in the code above isn't illegal, but showing that it is illegal, as you say, should be fairly simple. If for some choice of p, f, and g, we get the error "Identity law violated" or "Composition law violated", map does not form a valid functor. Here's an example with some selected values of p, f, and g https://jsfiddle.net/z22z8rLc/.

If some choices of p, f and g instead result in an "Unsuitable value" TypeError, this says nothing about the legality of the functor, since it is the same class of error as passing a -> b to traverse when b is not Applicative; a type error. This sort of thing is unavoidable in the absence of a type checker, and our options are to either pretend to be a type checker ourselves (throwing the TypeError), or to simply call it "unspecified behavior" and leave it at that. In both cases, the programmer needs to understand that their code is illegal and fix it; the spec isn't responsible for producing correct results from incorrect usage.

In case you're wondering, with a type checker (e.g. TypeScript) you can easily assert the non-thenability constraint statically, and thereby entirely prevent code that passes illegal morphisms from compiling.

[i-am-tom]

/shrug I've said my bit: I worry about misinterpretation. Ultimately, though, this is up to the collaborators within this repository, so I'm the wrong person to be talking to :sweat_smile: