scala - Scala+Cats でフリー モナドを使用して任意のツリーを使用する

Question

2 つの異なる解釈を持つ文法用のライブラリを作成しています。1) 文法に基づいて文字列を解析し、2) 文法によって定義された言語で文字列を生成します。

ライブラリは cat を使用して、文法の AST をフリー モナドとして作成します。しかし、自由なモナドは私の AST のリストのような表現を作成し、これはステートメント リストに適しているため、完全には適合しないように思われますが、文法はステートメント リストとはかけ離れており、任意のツリー構造にはるかに近いものです。

~演算子を使用して連結された 2 つの文法を示すことで、ツリーを実装することができました。AST は、それ自体が任意の AST である文法のリストです。

私の質問は: フリー モナドで 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サブツリーを再帰的に解釈するために、このケースでは安全でない再帰 (つまり、末尾再帰ではない) が使用されていることに特に注意してください。これを行うより良い方法はありますか？

ソースコードについては、ここをクリックしてください。