Skip to content

Instantly share code, notes, and snippets.

@DrBoolean
Created December 30, 2015 04:44
Show Gist options
  • Save DrBoolean/fdef9e08352ac42754f1 to your computer and use it in GitHub Desktop.
Save DrBoolean/fdef9e08352ac42754f1 to your computer and use it in GitHub Desktop.
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 `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' ]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment