scala - 有关点菜数据类型的问题

我正在阅读the original paper about data types a la carte，并决定尝试在Scala中实现该想法(我知道它已经在许多功能库中实现了)。不幸的是，我发现原始论文难以理解，一开始我就停留在某个地方。然后，我发现another paper更易于理解，并且设法将论文中的Haskell代码重写为Scala，您可以找到它here。但是我仍然在努力地理解一下:

第二篇论文的引文

原始Expr数据类型

data Expr = Val Int | Add Expr Expr

新型签名:

data Arith e = Val Int | Add e e

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

到底“我们已经绑定(bind)了签名的递归结”是什么意思？Fix Arith是与原始Expr等效的语言吗？
In的实际类型是In :: f (Fix f) -> Fix f如果我们尝试使用In构造和Val 1变量构造一个值，我们将得到以下结果:

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

相同数据类型的Scala编码:

  sealed trait Arith[A]
  case class Val[A](x: Int) extends Arith[A]
  case class Add[A](a: A, b: A) extends Arith[A]

  trait Fix[F[_]]
  case class In[F[_]](exp: F[Fix[F]]) extends Fix[F]

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函数，我将不胜感激。

引用本文:

最佳答案

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

data Expr = Val Int | Add Expr Expr

Arith类型通过用参数替换递归调用来“递归”递归:

data Arith e = Val Int | Add e e

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

Arith Void不能嵌套:它只能是文字值(Val n)，因为我们无法构造Add，因为我们无法获得Void类型的值(它没有构造函数)

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

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

等

Fix Arith给我们的是一种谈论深度不限的定点Arith (Arith (Arith …))的方法。

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

factorial' :: (Integer -> Integer) -> Integer -> Integer
factorial' recur n = if n <= 1 then 1 else n * recur (n - 1)

factorial :: Integer -> Integer
factorial = fix factorial'

factorial 5 == 120

Fix Arith表示的语言(语法)与Expr表示的语言等效。也就是说，它们是同构的:您可以编写一对总函数Fix Arith -> Expr和Expr -> Fix Arith。



我对Scala不太熟悉，但是Add似乎是Arith的子类型，因此可以用g类型的值填充F[Fix[F]]类型的Arith[Fix[Arith]]的参数，可以通过在In构造函数上进行匹配以“展开”一级递归。