如何为函数类型定义Monad ?

Question

我第一次尝试使用Scala 3，并且我正在尝试实现一组用于自学的解析器组合子;我卡住了tailRecM函数的定义为Monad。我把Functor和Applicative管理得很好。

我已经将我的类型定义为这样的函数:

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

对应的返回类型为:

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

我目前对tailRecM的定义如下:

@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 
}
}

如果我尝试构建，我得到"Found: Parsing.Parser[B] Required: Parsing.ParseResult[B]"为tailRecM(a)(fn)

据我所知，问题源于这样一个事实，即我的类型在问题Parser[A]是一个函数类型，而不仅仅是一个值类型?我试图通过修改tailRecM对tailRecM(a)(fn)(input)的递归调用来改善这个问题，但这显然不是堆栈安全的，也不会编译。

我如何解决这个问题，更广泛地说，我如何实现一般函数类型的Monad类型类?

Answer 1

不可能使tailRecM本身尾部递归;您需要定义一个尾递归helper方法

cats库如何为Function1实现tailRecM

def tailRecM[A, B](a: A)(fn: A => T1 => Either[A, B]): T1 => B =
(t: T1) => {
@tailrec
def step(thisA: A): B =
fn(thisA)(t) match {
case Right(b)    => b
case Left(nextA) => step(nextA)
}
step(a)
}

这是因为一元递归是互尾递归的一种形式，其中两个方法来回翻转彼此调用。scala编译器无法对其进行优化。因此，我们将一元部分的定义内联，而不是调用flatMap或其他方法

Answer 2

您需要再次将input传递给tailRecM调用

tailRecM(a)(fn)(input)

因为tailRecM(a)(fn)返回一个Parser，但是您需要从返回的Parser中获得ParserResult，正如您在所有其他情况下所做的那样。