Monoidal Contravariant Functors and Transducers

mcft.js

const daggy = require('daggy');
const {foldMap} = require('pointfree-fantasy')
const {concat, toUpper, prop, identity, range, compose} = require('ramda');

// Contravariant functors usually have this shape F(a -> ConcreteType).
// In other words, some type holding a function which is parametric on its input, but not output.
// They don't always have that shape, but it's a good intuition
// Covariant functors are what we're used to, which are parametric in their output
//================================================================

// Pred :: { run :: (a -> Bool) }
const Pred = daggy.tagged('run')


// Let's make Pred a monoid so we can combine them
// `concat` two Preds by running both and keeping the conjunction
// `empty` is a function that always returns true.
//
// This is basically the All monoid under the hood. We can make it more generic, by concatting the return values, but let's stick with this for now.
//=================================================

Pred.prototype.concat = function(g) {
  return Pred((x) => this.run(x) && g.run(x))
}

Pred.empty = () => Pred((_) => true)
Pred.prototype.empty = Pred.empty


// Hey! It has that (a -> ConcreteType) shape
// We can make it a Contravariant functor by providing a contramap
//=================================================================

// We can map over the `a` in `(a -> Bool)` by simply running `g` on the input, before it gets to the `run` function.
Pred.prototype.contramap = function(g) {
  return Pred(compose(this.run, g))
}

// Now, let's play with our monoidal contravariant predicates
//=================================================================
const greaterThan5 = (x) => x > 5
const lessThan20 = (x) => x < 20
const isOdd = (x) => !!(x % 2)


// int_combo :: Pred(Int -> Bool)
const int_combo = foldMap(Pred, [greaterThan5, lessThan20, isOdd]) // or int_combo = Pred(greaterThan5).concat(Pred(lessThan20)).concat(Pred(isOdd))

// string_combo :: Pred(String -> Bool)
const string_combo = int_combo.contramap(x => x.length)

range(0,30).filter(int_combo.run)
//=> [ 7, 9, 11, 13, 15, 17, 19 ]

["todd", "margaret", "katherine"].filter(string_combo.run)
//=> [ 'katherine' ]


// We were able to combine several predicates with `concat` as well as `contramap` to accept a different input. Cool!
//
// Let's look at a different one. Comparison. But first, a little setup.
//
// JavaScript sort() expects a return type of 1,0,-1. We should make an alias to make it easier to understand.
//=================================================================

// Ordering :: GT | LT | EQ
const GT = 1
const LT = -1
const EQ = 0

// Also, we are just aliasing this and not making a new type and everything. So instead of making a prototype based monoid on Orderings
// let's just use normal functions to use it as a monoid:
//=================================================================

const concatOrd = (o1, o2) => (o1 === EQ) ? o2 : o1
const emptyOrd = () => EQ

// That's a weird looking monoid instance, but it's pretty easy.
// If the first ordering is EQ, it uses the second one: o2. So if given to sort(), it acts like "sort by this, then by that"
//
// Time to make Comparison.
//=================================================================

// Comparison :: {compare :: (a -> a -> Ordering)
const Comparison = daggy.tagged('compare')


// We can make it a monoid since Ordering is a monoid. We just Compare two things and `concat` their outcome.
// `empty` starts with a function that always returns EQ
//=================================================================

Comparison.prototype.concat = function(c) {
  return Comparison((x, y) => concatOrd(this.compare(x, y), c.compare(x, y)))
}

Comparison.empty = () => Comparison((x, y) => EQ)
Comparison.prototype.empty = Comparison.empty


// There's that (a -> ConcreteType) shape again... It's a little different, but we still have parametric input and concrete output.
// Let's make a Comparison Contravariant Functor. Here we map over both the `a`s
//=================================================================

Comparison.prototype.contramap = function(f) {
  return Comparison((x,y) => this.compare(f(x), f(y)))
}


// And now to use it. Let's sort stuff by blackjack rules
//=================================================================

const eq21 = (a, b) => {
  if(a === 21) return GT
  if(b === 21) return LT
  return EQ
}

const over21 = (a, b) => {
  if(a > 21) return LT
  if(b > 21) return GT
  return EQ
}

const greater = (a, b) => {
  if(a > b) return GT
  if(b > a) return LT
  return EQ
}

const blackjack = foldMap(Comparison, [eq21, over21, greater])

range(15, 25).sort(blackjack.compare)
//=> [ 22, 23, 24, 15, 16, 17, 18, 19, 20, 21 ]


// It sorts worst-to-best hand.
// Let's use `contramap` to transform a set of cards to work since it takes ints
//=============================================================================

// cardToInt :: Card -> Int
const cardToInt = prop('val')

const cards = [{suit: 'hearts', val: 8}, {suit: 'diamonds', val: 4}, {suit: 'clubs', val: 7}]

cards.sort(blackjack.contramap(cardToInt).compare)
//=> [ { suit: 'diamonds', val: 4 }, { suit: 'clubs', val: 7 }, { suit: 'hearts', val: 8 } ]



// An interesting monoidal Contravariant Functor is a Transducer.
// Let's make the type
//=============================================================================

// Trans a b :: { build :: (r -> b -> r) -> (r -> a -> r) }
const Trans = daggy.tagged('build')


// This monoid instance is cool. It composes transducers for us. (e.g. mapper(f, filterer(g, cnct)))
//=============================================================================

Trans.prototype.concat = function(t1) {
  return Trans(cnct => this.build(t1.build(cnct)))
}

Trans.empty = () => Trans(identity)
Trans.prototype.empty = Trans.empty


// We can make it a Contravariant Functor:
// `contramap` will transform the element before it enters the transduction
//=============================================================================

Trans.prototype.contramap = function(f) {
  return Trans(cnct => (acc, x) => this.build(cnct)(acc, f(x)))
}

// And a normal Functor
// map will transform the element after it finishes the transduction
//=============================================================================

Trans.prototype.map = function(f) {
  return Trans(cnct => (acc, x) => this.build((acc1, x1) => cnct(acc1, f(x1)))(acc, x))
}

// Which means we can make it a Profunctor. A Profunctor is both covariant and contravariant.
// The Profunctor interfaces has a method called dimap.
//
// Here `dimap` will transform the element before and after it finishes the transduction
//=============================================================================

Trans.prototype.dimap = function(f, g) {
  return this.contramap(f).map(g)
}


// A transduce method that uses the foldable and monoid interfaces.
// Since build in Array doesn't have an empty, we must provide one.
//
// This `transduce` works for any foldable monoid.
// In other words, it expects an empty and concat method on the m and a reduce method on the i.
//=============================================================================

// transduce :: (Foldable f, Monoid m) => Trans a b -> m b -> f a -> m b
const transduce = (t, m, i) => i.reduce(t.build((acc, x) => acc.concat(x)), m.empty())

Object.defineProperty(Array, 'empty', {
  value: () => [],
  writable: true,
  configurable: true,
  enumerable: false
});


// Here are a couple of transducers
//=============================================================================

// filterer :: (a -> Bool) -> Trans a a
const filterer = (f) => Trans(cnct => (acc, x) => f(x) ? cnct(acc, x) : acc)

// mapper :: (a -> b) -> Trans a b
const mapper = (f) => Trans(cnct => (acc, x) => cnct(acc, f(x)))


// Let's play with this a bit.
//==================================

const users = [{name: 'Kilgore', age: 30}, {name: 'Trout', age: 20}]

const namesOfThoseOver21 = filterer(x => x.age > 21).concat(mapper(x => x.name))

const fakeId = (x) => ({name: x.name, age: 22})

transduce(namesOfThoseOver21, Array, users)
//=> [ 'Kilgore' ]

transduce(namesOfThoseOver21.contramap(fakeId), Array, users)
//=> [ 'Kilgore', 'Trout' ]

transduce(namesOfThoseOver21.map(toUpper), Array, users)
//=> [ 'KILGORE' ]

transduce(namesOfThoseOver21.dimap(fakeId, toUpper), Array, users)
//=> [ 'KILGORE', 'TROUT' ]