Using arbitrary trees with Free Monads in Scala+Cats

Question

I am creating a library for grammars that will have 2 different interpretations: 1) parsing strings based on the grammar 2) generating strings in the language defined by the grammar.

The library uses cats to create the AST of the grammar as a free monad. However, it seems like it may not be the perfect fit because the free monads create a list-like representation of my AST which is nice for statement lists, but a grammar is far from a statement list and much closer to an arbitrary tree structure.

I managed to implement my trees by using the ~ operator to denote 2 grammars that are concatenated. The AST is then a list of grammars that are themselves arbitrary ASTs.

My question is: What is a good way to recurse the subtrees of an AST in a free monad?

My current implementation 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
          }
        })
    }
}

Note especially, that the Multi case uses unsafe recursion (i.e. not tail recursive) in order to recursively interpret the subtree. Is there a better way to do this?

Please click here for the source code.

Answer 1

If you are building a Parser/Pretty printer library, the objects you are manipulating are probably not monads. You might want to use cats' InvariantMonoidal (and it's free conterpart, FreeInvariantMonoidal) instead. The associated tutorial has a section on codecs which you might find interesting.