traversable_laws.js

var Option = require('fantasy-options')
var Some = Option.Some;
var None = Option.None;

var Compose = function(x){
  this.val = x;
}

Compose.prototype.map = function(f){
  return new Compose(this.val.map(function(u){return u.map(f); }));
}

Compose.prototype.ap = function(c2){
  var composed_f = this.val.map(function(u){ return function(y){ return u.ap(y); } });
  return new Compose(composed_f.ap(c2.val));
}
Compose.of = function(x){ return new Compose(x) } // needs to do some crazy shit to find out inner functors

Some.prototype.traverse = function(f, of){
  return f(this.x).map(function(y){ return Some(y); });
}
None.prototype.traverse = function(f, of){
  return of(None)
}

Array.of = function(x){ return [x]; }

var _flatten = function(xs) { return xs.reduce(function(a,b){return a.concat(b);}, []) };
Array.prototype.ap = function(a2) {
  return _flatten(this.map(function(f){
    return a2.map(function(a){ return f(a); })
  }));
}

Array.prototype.traverse = function(f, of) {
  var cons_f = function(ys, x){
    return f(x).map(function(x){ return function(y){ return y.concat(x); } }).ap(ys);
  }
  return this.reduce(cons_f, of([]));
}

// Naturality
var u = ["John", "Ham"]

//+ t :: Option a -> [a]
var t = function(opt){
  return opt.cata({
    Some: function(x) { return [x] },
    None: function() { return [] }
  });
}
var f = function(x){ return Some(x+"burgler"); }
var nat1 = t(u.traverse(f, Option.of))
var nat2 = u.traverse(function(y){ return t(f(y)) }, Array.of)
// nat1 == nat2

// Identity
var u = ["Tetris Boss"]
var id1 = u.traverse(Identity, Identity.of)
var id2 = Identity(u)
// id1 == id2

// Composition
var u = ["Jimmy"]
var f = function(x){ return Some(x + " eat") }
var g = function(x){ return Some(x + " hello world") }
var of = function(x){ return new Compose(Some(Some(x))); }
var comp1 = u.traverse(function(x){ return new Compose(f(x).map(g)); }, of)
var comp2 = new Compose(u.traverse(f, Option.of).map(function(v){ return v.traverse(g, Option.of) }));
//comp1 == comp2

@wayneseymour Oh goodness, I didn't see this until now. Yes, of course we can do so, but I like to use the prototypes since we're just implementing interfaces after all. There are some projects that pass a dictionary of definitions around and when a type implements an interface it just appends to that dictionary.