f-algebra_of_lists.js

// cata alg = alg . fmap(cata alg) . unfix
function cata(alg, FixF) {
    return (i) => alg(FixF.fmap(cata(alg, FixF))(FixF.unfix(i)))
}

// ListF a x = NilF | ConsF a x
// where 'a' is the type of the values inside the list,
// whereas 'x' is the type on which the list will be evaluated (aka the carrier type)
const NilF = () => ({
    _tag: "NilF"
})
const ConsF = (value) => (carrier) => ({
    _tag: "ConsF",
    value,
    carrier
})
const ListF = {
    fmap(projection) {
        return (listF) => {
            if (listF._tag == "NilF") return NilF()
            // 'List a x' is a functor on 'x'
            else return ConsF(listF.value)(projection(listF.carrier))
        }
    },
    // the fix point of 'List a x' is emulated
    unfix(listFixed) {
        return listFixed.fixed
    },
    fix(listF) {
        return ({
            fixed: listF
        })
    }
}

// make a list algebra
const ListAlgebra = (onNilF, onConsF) => (listF) => {
  if (listF._tag == "NilF") return onNilF()
  else return onConsF(listF)
}

// 'x' of 'List a x' is array
const ArrayAlgebra = ListAlgebra(
  () => [], // onNilF
  (listF) => [listF.value, ...listF.carrier] // onConsF
)

// 'x' of 'List a x' is number
const SumAlgebra = ListAlgebra(
  () => 0, // onNilF
  (listF) => listF.value + listF.carrier // onConsF
)
     
// 'x' of 'List a x' is number
const ProdAlgebra = ListAlgebra(
  () => 1, // onNilF
  (listF) => listF.value * listF.carrier // onConsF
)

// 'x' of 'List a x' is string
const StringAlgebra = ListAlgebra(
  () => "nil", // onNilF
  (listF) => listF.value + "::" + listF.carrier // onConsF
)

// projection :: a -> b => 'x' of 'List a x' is 'List b'
const ProjectionAlgebra = (projection) => ListAlgebra(
  () => ListF.fix(NilF()), // onNilF
  (listF) => ListF.fix(ConsF(projection(listF.value))(listF.carrier)) // onConsF
)

// 'x' of 'List a x' is 'List a'
const PredicateAlgebra = (predicate) => ListAlgebra(
  () => ListF.fix(NilF()), // onNilF
  (listF) => predicate(listF.value) ? ListF.fix(ConsF(listF.value)(listF.carrier)) : listF.carrier // onConsF
)


// an instance where 'a' of 'List a x' is number
// list has to be considered as a 'Fix (List a x)' instance, that is 'List a': the fix point of 'List a x'
const list = ListF.fix(ConsF(4)(ListF.fix(ConsF(3)(ListF.fix(ConsF(2)(ListF.fix(ConsF(1)(ListF.fix(NilF())))))))))


// examples
console.log(cata(ArrayAlgebra, ListF)(list)) // [ 4, 3, 2, 1 ]
console.log(cata(SumAlgebra, ListF)(list)) // 10
console.log(cata(ProdAlgebra, ListF)(list)) // 24
console.log(cata(StringAlgebra, ListF)(list)) // "4::3::2::1::nil"
console.log(cata(ArrayAlgebra, ListF)(cata(ProjectionAlgebra(x => x * 10), ListF)(list))) // [ 40, 30, 20, 10 ]
console.log(cata(ArrayAlgebra, ListF)(cata(ProjectionAlgebra(String), ListF)(list))) // [ '4', '3', '2', '1' ]
console.log(cata(ArrayAlgebra, ListF)(cata(PredicateAlgebra(x => x % 2), ListF)(list))) // [3, 1]