# 'How to define a Monad for a function type?

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?

## Solution 1:^{[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.

## Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution | Source |
---|---|

Solution 1 | poki2 |