Scala 中的时态

Question

我正在学习递归模式，但我无法弄清楚未来同态和组织同态的用处。

我发现的几个 Scala 示例看起来非常没有说服力。我还找到了 Haskell 的例子，但我无法弄清楚它们。

假设我们有这样的函数：

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)

任何人都可以给出一些很好的 Scala 使用示例吗

• futu

  ？

• dynamo

  （

  histo

  内）应用于典型的动态规划问题？

“过去”和“未来”值的参考到底在哪里？

Answer 1

Recall futu 一次产生多个步骤，histo 一次消耗多个步骤。

以下是

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))))
}

Python 中的斐波那契

histo

示例，您可以自己翻译

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

作为参考，futu 和 cata 的定义（chrono 是它们的组合）

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))

这里的所有代码均取自https://github.com/Adam-Vandervorst/RecursionSchemes