时间戳

首页 > 解决方案 > Scala中具有相互递归类型的递归方案

scala - Scala中具有相互递归类型的递归方案

问题描述

给定以下数据类型：

sealed trait Expression
final case class Add(a: Expression, b: Expression) extends Expression
final case class Block(statements: List[Statement], result: Expression) extends Expression
    
sealed trait Statement
final case class ExpressionStatement(expression: Expression) extends Statement
final case class Assignment(variable: String, expression: Expression) extends Statement

我的第一步是执行以下操作：

sealed trait ExpressionF[E, S]
final case class AddF[E, S](a: E, b: E) extends ExpressionF[E, S]
final case class BlockF[E, S](statements: List[S], result: E) extends ExpressionF[E, S]
    
sealed trait StatementF[E, S]
final case class ExpressionStatementF(expression: E) extends StatementF[E, S]
final case class Print(expression: E) extends StatementF[E, S]

但我不确定如何将 Fix 与两个类型变量一起使用。

如何表示这些类型，以便可以使用 droste 或 matryoshka/Fix 使用递归方案？

标签： scalarecursion-schemes

解决方案

我认为为了处理相互递归的类型，您需要索引函子。我自己不太确定它是如何工作的，但这里有一个例子——不幸的是它在 Haskell 中。

https://gist.github.com/cstrahan/eab72b39884ef37b7a3c125f77e99a2e

这个库显然实现了相互递归类型的递归方案，但它同样在 Haskell 中并且基本上没有记录。但也许它仍然有帮助......

https://hackage.haskell.org/package/recursion-schemes-ix

推荐阅读