在Scala + Cats中使用带有Free Monads的任意树

Question

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

该库使用cat来创建语法的AST作为免费monad.然而,似乎它可能不是完美的契合,因为免费monad创建了我的AST的列表式表示,这对于语句列表很好,但是语法远离语句列表并且更接近任意树结构.

我设法通过使用~运算符来实现我的树,表示连接的2个语法.然后,AST是一个语法列表,它们本身就是任意的AST.

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

我目前的实现在这里:

 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情况使用不安全的递归(即不是尾递归)以递归地解释子树.有一个更好的方法吗？

请点击此处获取源代码.

Answer 1

如果您正在构建 Parser/Pretty 打印机库，您正在操作的对象可能不是 monad。您可能想使用“cats” InvariantMonoidal（它是免费的同类FreeInvariantMonoidal）来代替。相关教程中有一个关于编解码器的部分，您可能会感兴趣。