Using custom trees with Free Monads in Scala + Cats

Question

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

The library uses cats to create AST grammar as a free monad. However, this does not seem to be ideal, because free monads create a list view of my AST that works well for operator lists, but the grammar is far from the operator list and much closer to an arbitrary tree structure.

I managed to implement my trees using the ~ operator to denote 2 grammars that are combined. AST is a list of grammars that are themselves arbitrary AST.

My question is: what is a good way of recursing AST subtrees 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 that in the case of Multi , unsafe recursion (i.e., not recursive) is used to recursively interpret the subtree. Is there a better way to do this?

Please click here for source code.

Answer 1

If you create the Parser / Pretty printer library, the objects you manage are probably not monads. You might want to use InvariantMonoidal cats (and it's free conterpart, FreeInvariantMonoidal ). In the appropriate tutorial, a section on codecs that may seem interesting to you.