Chronomorphisms in Scala

Question

I'm learning recursion patterns, but I can't figure out the usefulness of futumorphism and histomorphism.

The couple of Scala examples I found look very unconvincing. I also found Haskell examples, but I can't figure them out.

Suppose we have functions like this:

def futu  [F[_]: Functor, X]: (X => Free[F, X]  ) => X => Fix[F]
def histo [F[_]: Functor, X]: (Cofree[F, X] => X) => Fix[F] => X

def ana   [F[_]: Functor, X]: (X => F[X]) => X => Fix[F]
def dynamo[F[_]: Functor, A, B]: (A => F[A], Cofree[F, B] => B) => A => B =  
  (coalg, alg) => ana(coalg) andThen histo(alg)

Can anyone give some good Scala examples of using

• futu?
• dynamo (histo within) applied to a typical dynamic programming problem?

And where exactly is the reference to "past" and "future" values ​​there?

Answer 1

Recall futu (right, green is Bind, red is Pure) produces multiple steps at a time, and histo (left, Red is CoFree) consumes multiple steps at a time. Below you're pretty-printing a superscript exponential expression by looking into the history, or inserting a binary Plus tree when parsing an associative expression.

Here are three examples of futu

// given the following function computes the adjacency list of an algebraic graph
def toAdj[V] = cata[[X] =>> Graph[V, X], Map[V, Set[V]]]{
  case Empty => Map()
  case Vertex(a) => Map(a -> Set())
  case Overlay(l, r) => l.mergeWith(r)(_ | _)
  case Connect(l, r) => l.mergeWith(r)(_ | _)
    .mergeWith(l.keySet.map((_, r.keySet)).toMap)(_ | _)
}
// this function creates an algebraic graph from an adjacency matrix
def fromAdj[K, V] = futu[[X] =>> Graph[V, X], Iterable[(V, Set[V])]]{
  case (v, nbs)::tail => Overlay(Free.Pure(tail), Free.Bind(
    Connect(Free.Bind(Vertex(v)),
            nbs.foldLeft(Free.Bind(Empty))((t, k) => Free.Bind(Overlay(t, Free.Bind(Vertex(k))))))))
  case Nil => Empty
}
// A simple algebraic graph constructor 
def path[V] = futu[[X] =>> Graph[V, X], Iterable[V]]{
  case x::y::Nil => Connect(Free.Bind(Vertex(x)), Free.Bind(Vertex(y)))
  case x::y::tail => Overlay(Free.Pure(x::y::Nil), Free.Pure(y::tail))
  case _ => Empty
}
// Converting a Tree instead
def tree[V] = futu[[X] =>> Graph[V, X], Tree[V]]{
  case Fix((v, Nil)) => Vertex(v)
  case Fix((v, xs)) =>
    val leaves = xs.collect[Free[[X] =>> Graph[V, X], Tree[V]]]{case Fix((s, _)) => Free.Bind(Vertex(s))}
    val branches = xs.collect[Free[[X] =>> Graph[V, X], Tree[V]]]{case x @ Fix((_, cs)) if cs.nonEmpty => Free.Pure(x)}
    val level = Connect(Free.Bind(Vertex(v)),
                        leaves.tail.foldLeft(leaves.head)((t, x) => Free.Bind(Overlay(t, x))))
    if branches.isEmpty then level
    else Overlay(Free.Bind(level),
                 branches.tail.foldRight(branches.head)((x, t) => Free.Bind(Overlay(t, x))))
}

And an example of Fibonacci histo in Python you can translate yourself

def fib_alg(fh):
    if isinstance(fh, Z): return 1
    elif isinstance(fh.pred.fa, Z): return 1
    else: return fh.pred.a + fh.pred.fa.pred.a

For reference, the definitions of futu and cata (chrono being their composite)

def futu[F[_] : Functor, A](coalg: A => F[Free[F, A]])(a: A): Fix[F] =
  def picking(ff: Free[F, A]): Fix[F] = ff match
    case Free.Pure(a) => futu(coalg)(a)
    case Free.Bind(ff) => Fix(ff.map(picking))
  Fix(coalg(a).map(picking))

def histo[F[_] : Functor, A](alg: F[CoFree[F, A]] => A)(fix: Fix[F]): A =
  def bundling(fix: Fix[F]): CoFree[F, A] =
    CoFree(histo(alg)(fix), fix.unFix.map(bundling))
  alg(fix.unFix.map(bundling))

All code here was taken from https://github.com/Adam-Vandervorst/RecursionSchemes