Recursion Schemes For Dynamic Programming: TS-Plus Edition

listr.ts

import type * as P from "@tsplus/stdlib/prelude/Covariant"
import type { Unfolder } from "@tsplus/stdlib/prelude/Recursive"
// Type definitions
export type MyNonEmptyList<A> = Leaf<A> | Node<A>
export type Carrier<A> = Tuple<[A, A]>
export interface ListF extends HKT {
  readonly type: MyNonEmptyList<this["A"]>
}

export const Functor: Covariant<ListF> = HKT.instance<P.Covariant<ListF>>({
  map: (f) => (fa) => fa.map(f)
})
export class Leaf<A> {
  readonly _tag = "leaf"
  readonly "_A": A
  constructor(readonly value: Carrier<string>) {
    return this
  }
  map<B>(_: (a: A) => B): MyNonEmptyList<B> {
    return this as any
  }
}
export class Node<A> {
  readonly _tag = "node"
  readonly "_A": A
  constructor(readonly head: Carrier<string>, readonly tail: A) {}
  map<B>(f: (r: A) => B): MyNonEmptyList<B> {
    return new Node(this.head, f(this.tail))
  }
}
export function substrings(s0: string): Unfolder.Fn<ListF, Carrier<string>> {
  return ({ tuple: [s, t] }) => {
    const [, ...ss] = s
    const [, ...ts] = t
    switch (s.length) {
      case 0:
        return t.length == 0 ?
          new Leaf(Tuple("", "")) :
          new Node(Tuple("", t), Tuple(s0, ts.join("")))
      default:
        return new Node(Tuple(s, t), Tuple(ss.join(""), t))
    }
  }
}

export const suffixes: Unfolder.Fn<ListF, string> = (curr) => {
  const [a, ...rest] = curr
  if (curr.length == 0 || !a) {
    return new Leaf(Tuple("", ""))
  }
  return new Node(Tuple(a, ""), rest.join(""))
}

recursive-example.ts

import type { ListF } from "./listr"
import { Functor, Node, substrings, suffixes } from "@tsplus/stdlib/examples/recursive/listr"
import type { Annotated } from "@tsplus/stdlib/prelude/Recursive"
import { Recursive } from "@tsplus/stdlib/prelude/Recursive"

function main() {
  editMain("kitten", "sitting")
  editMain("helicopter", "heliocopter")
  lcsMain("AGCAT", "GAC")
  lcsMain("GAC", "AGCAT")
  lisMain("carbohydrate")
  lisMain("assassination")
}
function editMain(s: string, t: string) {
  console.time(`editDistance ${s} => ${t}`)
  const value = editDistance(s, t)
  console.timeEnd(`editDistance ${s} => ${t}`)
  console.log(`editDistance ${s} => ${t} = ${value}`)
}
function lcsMain(s: string, t: string) {
  console.time(`lcs ${s} => ${t}`)
  const value = longestCommonSubsequence(s, t)
  console.timeEnd(`lcs ${s} => ${t}`)
  console.log(`lcs ${s} => ${t} = ${value}`)
}
function lisMain(s: string) {
  const label = `lis("${s}")`
  console.time(label)
  const value = longestIncreasingSequence(s)
  console.timeEnd(label)
  console.log(label + " = " + value)
}
// From https://www.researchgate.net/publication/221440162_Recursion_Schemes_for_Dynamic_Programming
// Typically, edit distance uses a matrix of substrings to store best previous value
// eg the "ate" vs "pit" matrix.  To find the previous values corresponding to insertion,
// deletion and substitution for the cell labeled "*" are marked
//     _ a t e _
//     p . . . .
//     i . * I .
//     t . D S .
// We emulate this using a "walk-of-value" matrix -- one stored as a list.
// For example
// ("ate", "pit"), ("te", pit"), ("e", "pit"), ("", "pit"), ("ate", "it"), ("te", "it") ....
//
// We use an annotated fold over the matrix to store each "cells" edit distance and
// use the string's length to lookup neighboring cells and the answer pops out at the head
function editDistance(s: string, t: string) {
  return pipe(
    Tuple(s, t),
    Recursive.unfold(Functor, substrings(s)),
    Recursive.$.foldAnnotated(Functor, editDistanceAnnotatedAlgebra(s.length))
  )
}
function editDistanceAnnotatedAlgebra(len: number): Annotated.Fn<ListF, number> {
  type AnnotatedNode = Node<Annotated<ListF, number>>
  return (fa) =>
    Match.tag(fa, {
      "leaf": () => 0,
      "node": minDistance
    })

  function minDistance({ head: { tuple: [[a], [b]] }, tail }: AnnotatedNode): number {
    return Math.min(
      lookup(0, tail) + 1, // insert
      lookup(len, tail) + 1, // delete
      lookup(len + 1, tail) + (a == b ? 0 : 1) // substitute
    )
  }
}

// We can also fold the same `substrings` structure to determine the longest common subsequence
function longestCommonSubsequence(s: string, t: string) {
  // this ensures a deterministic result
  const [a, b] = s.length < t.length ? [t, s] : [s, t]
  return pipe(
    Tuple(a, b),
    Recursive.unfold(Functor, substrings(a)),
    Recursive.$.foldAnnotated(Functor, longestCommonAlgebra(a.length))
  )
}

function longestCommonAlgebra(
  len: number
): Annotated.Fn<ListF, string> {
  type AnnotatedNode = Node<Annotated<ListF, string>>
  const max = Associative.max(Ord.number.contramap((_: string) => _.length))
  return (fa) =>
    Match.tag(fa, {
      "leaf": () => "",
      "node": longestSequence
    })

  function longestSequence({ head: { tuple: [[a], [b]] }, tail }: AnnotatedNode): string {
    return a == b ?
      (a + lookup(len + 1, tail)) :
      max.combine(lookup(0, tail), lookup(len, tail))
  }
}
function lookup<A>(n: number, cache: Annotated<ListF, A>): A {
  return n <= 0 ?
    cache.annotations :
    Match.tag(cache.caseValue, {
      "leaf": () => cache.annotations,
      "node": ({ tail }) => lookup(n - 1, tail)
    })
}
// And we can use an unfolder that generates `suffixes` of a string, along with an
// `Annotated.Fn` that picks the longest subsequence of the current character
function longestIncreasingSequence(s: string): string {
  return pipe(
    s,
    Recursive.unfold(Functor, suffixes),
    // since each step of our unfold will find the longest sequence
    // of just that character, we need an "empty" wrapper around the whole
    // thing so we can pick from the best
    (b) => Recursive.fix<ListF>(new Node(Tuple("", ""), b)),
    Recursive.$.foldAnnotated(Functor, longestIncreasingAlgebra())
  )
}

function longestIncreasingAlgebra(): Annotated.Fn<ListF, string> {
  type AnnotatedNode = Annotated<ListF, string>
  return (list) =>
    Match.tag(list, {
      "leaf": ({ value }) => value.at(0),
      "node": ({ head, tail }) => head.at(0) + findSmaller(head.at(0), tail)
    })

  function findSmaller(curr: string, start: AnnotatedNode): string {
    return iter("", start)

    function iter(accum: string, cache: AnnotatedNode): string {
      return Match.tag(cache.caseValue, {
        "leaf": () => accum,
        "node": ({ head, tail }) =>
          better(head.at(0), cache.annotations, accum) ?
            iter(cache.annotations, tail) :
            iter(accum, tail)
      })
    }
    function better(candidate: string, annotation: string, accum: string) {
      return (Ord.string.compare(curr, candidate) < 0) &&
        annotation.length > accum.length
    }
  }
}
main()

Example of three common dynamic programming algorithms implemented using TS-Plus' Recursive.foldAnnotated functions. From the paper https://www.researchgate.net/publication/221440162_Recursion_Schemes_for_Dynamic_Programming