Deriving free instances in JS

deriving.js

// Instances
const Arr = (() => {
  // Monoid instance (forall a, [a] is a Monoid)
  // :: [a]
  const empty = []
  // :: [a] -> [a] -> [a]
  const concat = a => b => a.concat(b)

  // Traversable instance (we have no typeclass system, so we need to accept the applicative instance dictionary explicitly)
  // :: { "of" :: a -> f a, "lift2": (a -> b -> c) -> f a -> f b -> fc }
  //    -> (a -> f b)
  //    -> [a]
  //    -> f [b]
  const traverse = A => f => a => a.map(f).reduce((p, c) => A.lift2(concat)(p)(A.of(c)), A.of(empty))

  return { empty, concat, traverse }
})()

const Fn = (() => {
  // :: x -> x
  const id = x => x
  return { id }
})()

const Identity = (() => {
  // :: (a -> b) -> a -> b
  const map = Fn.id
  // :: a -> a
  const of = Fn.id
  // :: (a -> b -> c) -> a -> b -> c
  const lift2 = Fn.id
  
  return { map, of, lift2 }
})()

// Our derivation (works for any traversable)
// :: { "traverse" :: (same as type of traverse above, with [a] substituted for t a) } -> (a -> b) -> t a -> t b
const mapFromTraverse = ({ traverse }) => traverse(Identity)
const map = mapFromTraverse(Arr)

console.log(map(x => x * 2)([1, 2, 3]))
// [2, 4, 6]