Monoidal Contravariant Functors and Transducers

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 as //=================================================================

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' ]