How to define a Monad for a function type?

Question

I am trying Cats for the first time and am using Scala 3, and I am trying to implement a set of parser combinators for self-pedagogy, however; I am stuck on the definition of the tailRecM function for Monad. I have managed Functor and Applicative just fine.

I have defined my type in question as a function such that:

type Parser[A] = (input: List[Token]) => ParseResult[A]

with corresponding return types as:

type ParseResult[A] = Success[A] | Failure 
case class Success[A](value: A, tokens: List[Token])
case class Failure(msg: String, tokens: List[Token])

My current definition of tailRecM is as follows:

@annotation.tailrec
def tailRecM[A, B](init: A)(fn: A => Parser[Either[A, B]]): Parser[B] =
  (input: List[Token]) => 
    fn(init)(input) match {
      case f: Failure => f
      case s: Success[Either[A, B]] => s.value match {
        case Right(b) => Success(b, s.tokens)
        case Left(a) => tailRecM(a)(fn) // won't compile 
      }
  }

If I attempt to build I get "Found: Parsing.Parser[B] Required: Parsing.ParseResult[B]" for tailRecM(a)(fn)

The issue as far as I can tell stems from the fact that my type in question Parser[A] is a function type and not simply a value type? I attempted to ameliorate the issue by modifying the tailRecM recursive call to tailRecM(a)(fn)(input) but then this is obviously not stack safe, and also will not compile.

How can I resolve this issue, and more broadly, how can I implement the Monad typeclass for function types in general?

Answer 1

You need to pass the input again to the tailRecM call

tailRecM(a)(fn)(input)

because tailRecM(a)(fn) returns a Parser, but you need the ParserResult from that returned Parser, as you already did in all other cases.