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

该库使用cat来创建语法的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.