了解 scalaz 中的自由 monad

Question

我正在 Scalaz 中尝试使用 Free monad 并尝试构建简单的解释器来解析和评估如下表达式：

dec(inc(dec(dec(10)))

其中dec表示递减，inc表示递增。这是我得到的：

trait Interpreter[A]
case class V[A](a: A) extends Interpreter[A]

object Inc {
  private[this] final val pattern = Pattern.compile("^inc\((.*)\)$")
  def unapply(arg: String): Option[String] = {
    val m = pattern.matcher(arg)
    if(m.find()){
      Some(m.group(1))
    } else None
  }
}

object Dec {
  private[this] final val pattern = Pattern.compile("^dec\((.*)\)$")
  def unapply(arg: String): Option[String] = {
    val m = pattern.matcher(arg)
    if(m.find()){
      Some(m.group(1))
    } else None
  }
}

object Val {
  def unapply(arg: String): Option[Int] =
    if(arg.matches("^[0-9]+$")) Some(Integer.valueOf(arg))
    else None
}

现在这就是我构建 AST 所需的全部内容。目前看起来如下：

def buildAst(expression: String): Free[Interpreter, Int] = 
   expression match {
     case Inc(arg) => inc(buildAst(arg))
     case Dec(arg) => dec(buildAst(arg))
     case Val(arg) => value(arg)
}

private def inc(i: Free[Interpreter, Int]) = i.map(_ + 1)
private def dec(d: Free[Interpreter, Int]) = d.map(_ - 1)
private def value(v: Int): Free[Interpreter, Int] = Free.liftF(V(v))

现在测试应用程序时：

object Test extends App{

  val expression = "inc(dec(inc(inc(inc(dec(10))))))"

  val naturalTransform = new (Interpreter ~> Id) {
    override def apply[A](fa: Interpreter[A]): Id[A] = fa match {
      case V(a) => a
    }
  }

  println(buildAst(expression).foldMap(naturalTransform)) //prints 12
}

而且效果很好（我不确定它是否是 scalaz 风格）。

问题是提取器对象 Inc、Dec、Val 感觉样板代码。有没有办法减少这样的代码重复。

如果支持的功能越来越多，这肯定会成为一个问题。

Answer 1

自由 monad 正在创建一些样板，这是事实。但是，如果您愿意遵守一些约定，您可以使用 Freasy Monad:

重写解释器

@free trait Interpreter {
  type InterpreterF[A] = Free[InterpreterADT, A]
  sealed trait InterpreterADT[A]


  def inc(arg: InterpreterF[Int]): InterpreterF[Int]
  def dec(arg: InterpreterF[Int]): InterpreterF[Int]
  def value(arg: Int): InterpreterF[Int]
}

这将生成所有案例类并匹配它们。解释器只是一个要实现的特征。

但是，您在 unapply 中已经有一些逻辑 - 因此您必须拆分解析和执行逻辑：

import Interpreter.ops._
val incP = """^inc\((.*)\)$""".r
val decP = """^dec\((.*)\)$""".r
val valP = """^val\((.*)\)$""".r
def buildAst(expression: String): InterpreterF[Int] = expression match {
  case incP(arg) => inc(buildAst(arg))
  case decP(arg) => dec(buildAst(arg))
  case valP(arg) => value(arg.toInt)
}

然后你可以实现一个实际的解释器：

val impureInterpreter = new Interpreter.Interp[Id] {
  def inc(arg: Int): Int = arg+1
  def dec(arg: Int): Int = arg-1
  def value(arg: Int): Int = arg
}

和运行它：

impureInterpreter.run(buildAst(expression))

我承认这更像是一个伪代码，而不是经过测试的工作解决方案，但它应该给出一个总体思路。另一个使用类似想法的库是 Freestyle 但他们使用自己的免费 monads 实现而不是依赖 cats/scalaz.

因此，我认为只要您对拆分解析和解释没有问题，就可以删除一些样板文件。当然不是所有的都可以删除 - 你必须在你的 Interpreter 代数上声明可能的操作，并且你必须自己实现解释器。

了解 scalaz 中的自由 monad

Understanding Free monad in scalaz

scala

scalaz

free-monad