Scala cats 中递归算术表达式的免费单子
Free monads for recursive arithmetic expressions in Scala cats
我正在尝试使用 Scala cats library and following the tutorial doc 定义一个简单的算术表达式求值器。
目标是以模块化方式定义 DSL,结合可以单独定义的整数值和加法。
我有以下代码:
package examples
import cats._
import cats.data._
import cats.free._
import cats.free.Free._
import scala.language.higherKinds
object FreeExpr {
sealed trait ValueF[A]
case class IntValue(n: Int) extends ValueF[Int]
class Value[F[_]](implicit I: Inject[ValueF, F]) {
def intVal(n:Int): Free[F,Int] = inject[ValueF,F](IntValue(n))
}
object Value {
implicit def value[F[_]](implicit I: Inject[ValueF,F]): Value[F] = new Value[F]
}
sealed trait ArithF[A]
case class Add[A](x: A, y: A) extends ArithF[A]
class Arith[F[_]](implicit I: Inject[ArithF, F]) {
def add[A](x: A, y: A) : Free[F,A] =
Free.inject[ArithF,F](Add(x,y))
}
object Arith {
implicit def arith[F[_]](implicit I: Inject[ArithF,F]): Arith[F] = new Arith[F]
}
type Expr[A] = Coproduct[ArithF, ValueF, A]
type Result[A] = Id[A]
object ArithId extends (ArithF ~> Result) {
def apply[A](fa: ArithF[A]) = fa match {
case Add(x,y) => ??? // for { m <- x; n <- y } yield (m + n)
}
}
object ValueId extends (ValueF ~> Result) {
def apply[A](fa: ValueF[A]) = fa match {
case IntValue(n) => Monad[Id].pure(n)
}
}
val interpreter: Expr ~> Result = ArithId or ValueId
def expr1(implicit value : Value[Expr],
arith : Arith[Expr]): Free[Expr, Int] = {
import value._, arith._
for {
n <- intVal(2)
m <- add(n, n)
} yield m
}
lazy val run1 = expr1.foldMap(interpreter)
}
前面的代码编译是因为我为 Add 案例注释了 "apply" 的定义。我最初认为解决方案是注释的代码,但编译器 returns:
[error] ...FreeExpr.scala:40: value flatMap is not a member of type parameter A
[error] case Add(x,y) => for { m <- x; n <- y } yield (m + n)
[error] ^
你知道我需要在代码中更改什么才能以模块化方式定义 DSL 和解释器吗?
问题是 Add
的结果类型过于笼统,在 case Add(x,y) => ...
中,值 x
和 y
的类型改为 A
M[A]
个。
我找到了两个可能的解决方案。
一个是把Add
的定义改成case class Add(x:Int,y:Int)
,把解释器的定义改成
object ArithId extends (ArithF ~> Result) {
def apply[A](fa: ArithF[A]) = fa match {
case Add(x,y) => x + y
}
}
我已将此解决方案添加到此要点:FreeExprInt.scala
先前解决方案的一个问题是结果类型被固定为 Int
,它可能更有趣,至少是 Semigroup
。
我尝试使用 case class Add[A: Semigroup](x: A, y: A)
来定义它,但似乎编译器在处理第二个隐式参数列表时遇到了一些问题。
一种可能的解决方法是明确添加证据。我将此解决方案添加到另一个要点:FreeExprExplicit.scala
虽然这两种解决方案都有效,但我对它们不太满意,因为我更喜欢结果类型可以是任何 A
.
的更通用的解决方案
有人建议我看一下无标签最终样式 (Alternatives to GADTs),但我还没有实现它。
我正在尝试使用 Scala cats library and following the tutorial doc 定义一个简单的算术表达式求值器。
目标是以模块化方式定义 DSL,结合可以单独定义的整数值和加法。
我有以下代码:
package examples
import cats._
import cats.data._
import cats.free._
import cats.free.Free._
import scala.language.higherKinds
object FreeExpr {
sealed trait ValueF[A]
case class IntValue(n: Int) extends ValueF[Int]
class Value[F[_]](implicit I: Inject[ValueF, F]) {
def intVal(n:Int): Free[F,Int] = inject[ValueF,F](IntValue(n))
}
object Value {
implicit def value[F[_]](implicit I: Inject[ValueF,F]): Value[F] = new Value[F]
}
sealed trait ArithF[A]
case class Add[A](x: A, y: A) extends ArithF[A]
class Arith[F[_]](implicit I: Inject[ArithF, F]) {
def add[A](x: A, y: A) : Free[F,A] =
Free.inject[ArithF,F](Add(x,y))
}
object Arith {
implicit def arith[F[_]](implicit I: Inject[ArithF,F]): Arith[F] = new Arith[F]
}
type Expr[A] = Coproduct[ArithF, ValueF, A]
type Result[A] = Id[A]
object ArithId extends (ArithF ~> Result) {
def apply[A](fa: ArithF[A]) = fa match {
case Add(x,y) => ??? // for { m <- x; n <- y } yield (m + n)
}
}
object ValueId extends (ValueF ~> Result) {
def apply[A](fa: ValueF[A]) = fa match {
case IntValue(n) => Monad[Id].pure(n)
}
}
val interpreter: Expr ~> Result = ArithId or ValueId
def expr1(implicit value : Value[Expr],
arith : Arith[Expr]): Free[Expr, Int] = {
import value._, arith._
for {
n <- intVal(2)
m <- add(n, n)
} yield m
}
lazy val run1 = expr1.foldMap(interpreter)
}
前面的代码编译是因为我为 Add 案例注释了 "apply" 的定义。我最初认为解决方案是注释的代码,但编译器 returns:
[error] ...FreeExpr.scala:40: value flatMap is not a member of type parameter A
[error] case Add(x,y) => for { m <- x; n <- y } yield (m + n)
[error] ^
你知道我需要在代码中更改什么才能以模块化方式定义 DSL 和解释器吗?
问题是 Add
的结果类型过于笼统,在 case Add(x,y) => ...
中,值 x
和 y
的类型改为 A
M[A]
个。
我找到了两个可能的解决方案。
一个是把Add
的定义改成case class Add(x:Int,y:Int)
,把解释器的定义改成
object ArithId extends (ArithF ~> Result) {
def apply[A](fa: ArithF[A]) = fa match {
case Add(x,y) => x + y
}
}
我已将此解决方案添加到此要点:FreeExprInt.scala
先前解决方案的一个问题是结果类型被固定为 Int
,它可能更有趣,至少是 Semigroup
。
我尝试使用 case class Add[A: Semigroup](x: A, y: A)
来定义它,但似乎编译器在处理第二个隐式参数列表时遇到了一些问题。
一种可能的解决方法是明确添加证据。我将此解决方案添加到另一个要点:FreeExprExplicit.scala
虽然这两种解决方案都有效,但我对它们不太满意,因为我更喜欢结果类型可以是任何 A
.
有人建议我看一下无标签最终样式 (Alternatives to GADTs),但我还没有实现它。