Hylo MergeSort

hylo-mergesort.js

// recursively deconstruct a functor by the given `alg` function
const cata = alg => x => alg(x.map(cata(alg)))

// recursively construct a functor by the given `coAlg` function
const ana = coAlg => x => coAlg(x).map(ana(coAlg))

// `hylo(alg, coAlg)` equivalent to `compose(cata(alg), ana(coAlg))`
// performed in a single pass
const hylo = (alg, coAlg) => function go(x) {
  return alg(coAlg(x).map(go))
}

// constructors representing a binary tree
const Empty =
  ({ map: returnThis, match: cases => cases['Empty']() })
const Leaf = x =>
  ({ map: returnThis, match: cases => cases['Leaf'](x) })
const Node = (l, r) =>
  ({ map: f => Node(f(l), f(r)), match: cases => cases['Node'](l, r) })
function returnThis() { return this }

// non-recursive transformation of a list to a tree
const listToTree = (xs) =>
  xs.length === 0 ? Empty :
  xs.length === 1 ? Leaf(xs[0]) :
                    Node(xs.slice(0, xs.length / 2),
                         xs.slice(xs.length / 2))

// non-recursive transformation of a tree to a sorted list
const treeToList = tree => tree.match({
  Empty: () => [],
  Leaf: (x) => [x],
  Node: mergeLists
})

// merge two sorted lists together
const mergeLists = (xs, ys) =>
  xs.length === 0 ? ys :
  ys.length === 0 ? xs :
  xs[0] <= ys[0]  ? [xs[0], ...mergeLists(xs.slice(1), ys)] :
                    [ys[0], ...mergeLists(xs, ys.slice(1))]

const mergeSort = hylo(treeToList, listToTree)

mergeSort([2, 1, 4, 3, 0])