有关点菜数据类型的问题

Question

我正在阅读有关数据点菜的原始文章，并决定尝试在Scala中实现这一想法（我知道它已经在许多功能库中实现了）。不幸的是，我发现原始论文很难理解，一开始我就停留在某个地方。然后，我发现了另一篇更容易理解的论文，并且设法将论文中的Haskell代码重写为Scala，您可以在这里找到它。但是我仍然在努力地理解一些时间：

1. 引用第二篇论文

原始Expr数据类型

data Expr = Val Int | Add Expr Expr

新型签名：

data Arith e = Val Int | Add e e

对于任何函子f，其诱导的递归数据类型Fix f定义为的最小固定点f，实现如下：

data Fix f = In (f (Fix f))

现在我们已经绑定了签名的递归结，这Fix Arith是一种等效于原始Expr数据类型的语言， 该语言允许整数值和加法运算。

“我们已经绑定了签名的递归结”到底是什么意思？Fix Arith与原始语言等效的语言是什么意思Expr？

的实际类型In是In :: f (Fix f) -> Fix f 如果我们尝试使用InConstruct和Val 1Variable 构造一个值，我们将得到以下结果：

> :t  In(Val 1)
> In(Val 1) :: Fix Arith

相同数据类型的Scala编码：

data Expr = Val Int | Add Expr Expr

2. fold函数该fold函数具有以下签名和实现

Haskell：

fold :: Functor f => (f a -> a) -> Fix f -> a
fold f (In t) = f (fmap (fold f) t)

我想出的Scala变体

  def fold[F[_] : Functor, A](f: F[A] => A): Fix[F] => A = {
    case In(t) =>
      val g: F[Fix[F]] => F[A] = implicitly[Functor[F]].lift(fold(f))
      f(g(t))
  }

我很好奇的事情是，在我的Scala版本的功能g有如下类型F[Fix[F]] => F[A]，但变量的类型t后，模式匹配是LaCarte$Add与价值Add(In(Val(1)),In(Val(2)))，它是如何发生的，它的有效适用的功能g来LaCarte$Add？另外，如果您能帮助我理解fold功能，我将不胜感激。

引用本文：

fold的第一个参数是f代数，它提供了与给定签名关联的每个构造函数的行为f。

Answer 1

\n

\xe2\x80\x9c 我们已经将签名 \xe2\x80\x9d 的 \xe2\x80\x98 递归结 \xe2\x80\x99 绑在一起，这到底意味着什么？

\n

\n\n

原始Expr数据类型是递归的，在自己的定义中引用自身：

\n\n

data Expr = Val Int | Add Expr Expr\n

\n\n

这Arith\xe2\x80\x9c 通过用参数替换递归调用来分解 \xe2\x80\x9d 递归：

\n\n

data Arith e = Val Int | Add e e\n

\n\n

原始Expr类型可以有任意深度的嵌套，我们也希望支持Arith，但最大深度取决于我们选择的类型e：

\n\n

\n

• Arith Void可以\xe2\x80\x99t 嵌套：它只能是一个文字值 ( Val n)，因为我们可以\xe2\x80\x99t 构造一个Add，因为我们可以\xe2\x80\x99t 获取类型的值Void（它没有构造函数）

\n

• Arith (Arith Void)可以有一层嵌套：外部构造函数可以是Add，但内部构造函数只能是Lit。

\n

• Arith (Arith (Arith Void))可以有两个级别

\n

• 等等

\n

\n\n

给我们提供的是一种不受深度限制的Fix Arith讨论不动点的方法。 Arith (Arith (Arith \xe2\x80\xa6))

\n\n

这就像我们如何用非递归函数替换递归函数并使用定点组合器恢复递归一样：

\n\n

data Expr = Val Int | Add Expr Expr\n

\n\n

\n

Fix Arith与原文等效的语言是什么意思Expr？

\n

\n\n

所表示的语言（语法）Fix Arith与所表示的语言是等价的Expr；也就是说，它们\xe2\x80\x99是同构的：你可以编写一对总函数Fix Arith -> Expr和Expr -> Fix Arith。

\n\n

\n

it\xe2\x80\x99s 如何有效地将函数g应用于LaCarte$Add？

\n

\n\n

I\xe2\x80\x99m 对 Scala 不是很熟悉，但它看起来Add是 的子类型，因此typeArith的参数可以填充通过在构造函数上匹配 \xe2\x80\得到的类型值x9cunfold\xe2\x80\x9d 一级递归。gF[Fix[F]]Arith[Fix[Arith]]In

\n