1

给定以下数据类型:

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 使用递归方案?

4

1 回答 1

1

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

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

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

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

于 2020-08-14T18:10:20.767 回答