scala - 在 Scala+Cats 中使用任意树和 Free Monads

Question

我正在为语法创建一个库，它将有 2 种不同的解释:1) 根据语法解析字符串 2) 以语法定义的语言生成字符串。

该库使用猫来创建语法的 AST 作为一个免费的 monad。然而，似乎它可能并不完美，因为自由 monad 创建了我的 AST 的类似列表的表示，这对语句列表很好，但语法与语句列表相去甚远，更接近于任意树结构。

我设法使用 ~ 实现了我的树。运算符来表示连接的 2 个文法。 AST 是一个语法列表，这些语法本身就是任意的 AST。

我的问题是:在自由 monad 中递归 AST 的子树的好方法是什么？

我当前的实现 is here:

 def parserInterpreter: GrammarA ~> ParserInterpreterState =
new (GrammarA ~> ParserInterpreterState) {
  def apply[A](fa: GrammarA[A]): ParserInterpreterState[A] =
    fa match {
      case Regx(regexp) => parseRegex(regexp)
      case Optional(b)  => parseOptional(b.foldMap(this))
      case m @ Multi(g) =>
        def x: State[String, A] =
          State.apply(state => {
            g.foldMap(this)
              .run(state)
              .map {
                case (s, ParseSuccess(_))    => x.run(s).value
                case r @ (s, ParseFailure()) => (s, ParseSuccess(s).asInstanceOf[A])
              }
              .value
          })
        x
      case Choice(a, b) =>
        State.apply(state => {
          val runA = a.foldMap(this).run(state).value
          if (runA._2.asInstanceOf[ParseResult[_]].isSuccess)
            runA
          else {
            b.foldMap(this).run(state).value
          }
        })
    }
}

特别注意，Multi case 使用不安全递归(即非尾递归)来递归解释子树。有一个更好的方法吗？

Please click here for the source code.

Answer 1

如果您正在构建 Parser/Pretty 打印机库，则您正在操作的对象可能不是 monad。您可能想使用猫的 InvariantMonoidal (而且它是免费的， FreeInvariantMonoidal )代替。相关教程有a section在您可能会感兴趣的编解码器上。