Equivalent definitions

[masaeedu]

Certain typeclasses can be satisfied using one of several equivalent minimal definitions. For example Traversable, which can be satisfied by defining either of sequence or traverse, or Bifunctor, which can be satisfied by defining either of bimap or lmap + rmap.

It is necessary that for each equivalent minimal definition, there exist universally applicable derivations of all the other definitions. As a practical example, it is possible to define both lmap and rmap given a definition of bimap:

const deriveLMapAndRMap = ({ bimap }) => ({
  lmap: f => bimap(f)(x => x),
  rmap: f => bimap(x => x)(f)
})

Similarly, it is possible to derive bimap given both lmap and rmap:

const deriveBimap = ({ lmap, rmap }) => ({
  bimap: f => g => compose(lmap(f))(rmap(g))
})

Hence the two definitions are totally isomorphic, and either should do for defining Bifunctor. While this case is rather trivial, there are other classes where the equivalence between minimal defs may have significant differences. For example, fantasy-land requires users to define reduce to implement Foldable, whereas it may be more convenient or performant to define foldMap for certain kinds of foldables.

An implementer of a class instance for which there are multiple equivalent definitions should have the flexibility to satisfy any one of the minimal definitions (for reasons of clarity/performance), and claim compliance with the spec. The spec should specify derivations of common minimal definitions from each other (as part of the laws).

---

This concept extends past equivalent definitions within a single class. Certain typeclasses have "intrinsic" superclasses, for which the entire implementation of the superclass instance may simply be obtained for free from the child instance.

For example, Functor and Applicative are "intrinsic" superclasses of Monad, so in practical terms defining a monadic functor instance just comes down to defining of + chain. All the other things (lift2/ap, map) can simply be derived from those two methods. You might also choose to implement the equivalent definition join + map instead of of + chain (and in fact this might have a significant performance impact for certain kinds of monads).

There's many more examples (traverse gives you both map and reduce/foldMap), but I think that illustrates the gist of the problem. In case you're interested in looking through more equivalent definitions, I have several more that I'm using day to day in https://github.com/masaeedu/fp. Here for example are some derivations of map from implementations of the subclasses of Functor.

---

The fantasy land spec should provide a vocabulary for talking about equivalent minimal definitions of typeclasses, and should accommodate common equivalent definitions of the classes it specifies.

[davidchambers]

This seems reasonable to me. The derivations could be defined in sanctuary-type-classes so Z.map, for example, could operate on a value which provides fantasy-land/bimap but not fantasy-land/map.

We should consider the pros and cons of the derivations living in sanctuary-type-classes as opposed to in a dedicated derivations package.

Option 1

1. Author defines an algebraic data type.
2. Author imports the derivations package and uses it to fill in the gaps.
3. Author releases a package with all appropriate methods defined.
4. Users interact with the ADT via functions provided by sanctuary-type-classes or another library.

Option 2

1. Author defines an algebraic data type.
2. Author releases a package with the minimal number of methods defined.
3. Users interact with the ADT via functions provided by sanctuary-type-classes or another library.
4. These functions use derivations when necessary.