sumOfProducts.js

const Generic = (() => {
  const unit = Symbol('unit')
  const sum = Symbol('sum')
  const prod = Symbol('prod')
  const val = Symbol('val')
  const con = Symbol('con')
  const dat = Symbol('dat')
  const recur = Symbol('recur') // pass as 2nd arg of val to indicate recursion/nesting
  const Unit = { meta: unit }
  const Sum = a => b => ({ value: { left: a, right: b }, meta: sum })
  const Prod = a => b => ({ value: [a, b], meta: prod })
  const Val = n => a => t => ({ value: a, name: n, meta: val, tag: t })
  
  // You don't need to use these (they have no direct effect right now), 
  // but you can if you want additional metadata:
  // Constructor wrapper
  const Con = n => a => ({ value: a, name: n, meta: con })
  // Datatype wrapper
  const Dat = n => a => ({ value: a, name: n, meta: dat })

  const match = ({ Unit, Sum, Prod, Val, Con, Dat }) => ({value, meta, name, tag}) => {
    switch (meta) {
      case unit:
        return Unit
      case sum:
        const { left, right } = value
        return Sum(left)(right)
      case prod:
        const [a, b] = value
        return Prod(a)(b)
      case val:
        return Val(name)(value)(tag)
      case con:
        return Con(name)(value)
      case dat:
        return Dat(name)(value)
      default:
      	const o = { value, meta, name, tag }
        console.log('[Invalid Generic]', o)
        throw Error(`Invalid Generic!`)
    }
  }
  
  // this is actually more like `over` from lens, except it takes
  // the name of a Val instead of an actual lens (todo?)
  // it is equivalent to fmap if you use it properly.
  const gmap = n => f => {
    const rec = (a) => gmap(n)(f)(a)
    return match({
      Unit,
      Sum: left => right => left ? Sum(rec(left))() : Sum()(rec(right)),
      Prod: a => b => Prod(rec(a))(rec(b)),
      Val: _n => a => t => {
      	if (_n === n) return Val(_n)(f(a))(t)
        if (t === recur) return Val(_n)(rec(a))(t)
        return Val(_n)(a)(t)
      },
      Con: n => a => Con(n)(rec(a)),
      Dat: n => a => Dat(n)(rec(a))
    })
  }
  
  return { recur, Unit, Sum, Prod, Val, Con, Dat, match, gmap }
})()

const { recur, Sum, Prod, Val, gmap } = Generic

// ----------------------------------- EXAMPLE USAGE ---------------------------------------

const List = (() => {
  // Algebra
  const Nil = undefined;
  const Cons = x => xs => ({ x, xs });
  const match = ({ Nil, Cons }) => l => {
    if (l === undefined) return Nil;

    const { x, xs } = l;
    return Cons(x)(xs);
  };
  
  const G = Generic
  
  // Obviously this is way too much boilerplate,
  // but toRep and fromRep can be mechanically derived using match and a "shape" description
  const toRep = l => {
    const r = match({
      Nil: G.Sum(G.Con('Nil')(G.Unit))(),
      Cons: x => xs => G.Sum()(G.Con('Cons')(
        G.Prod
          (G.Val('a')(x)())
          (G.Val('tail')(toRep(xs))(G.recur))
      ))
    })(l)
    return G.Dat('List')(r)
  }
  
  const lfail = (m) => { throw Error(`[List.fromRep]: ${m}`) }
  
  const fromRep = G.match({
    Dat: n => a => n === 'List' ? fromRep(a) : lfail(`Not a List: ${n}`),
    Con: n => a => n === 'Cons' || n === 'Nil' ? fromRep(a) : lfail(`Not a List constructor: ${n}`),
    Sum: l => r => l ? fromRep(l) : fromRep(r),
    Prod: x => xs => Cons(fromRep(x))(fromRep(xs)),
    Val: n => a => t => {
      if (n === 'a') return a
      if (n === 'tail' && t === G.recur) return fromRep(a)
      lfail(`Invalid data in Cons rep, name: ${n}, value: ${v}, tage: ${t}`)
    },
    Unit: Nil
  })
  
  // now we can derive map:
  const map = f => xs => fromRep(G.gmap('a')(f)(toRep(xs)))
  
  return { Nil, Cons, match, toRep, fromRep, map };
})();

// gmap is like fmap if you use it functor-ly:
const { Cons, Nil } = List
const l = Cons(1)(Cons(2)(Cons(3)(Nil)))
console.log(List.map(x => x + 1)(l))

// gmap is not like fmap if you don't use it functor-ly:
// t :: Either (Either () Int) ()
const t = Sum(Val('b')(Sum()(Val('a')(10)()))(recur))()
console.log(gmap('a')(x => { return x + 1 })(t))