如何为函数类型定义单子？

Question

我正在第一次尝试猫，并且正在使用Scala 3，但是我正在尝试实施一组解析器组合者以自行自同学。我被关注tailRecm单元的函数的定义。我已经管理函数和应用程序。

我将所讨论的类型定义为一个函数：

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

如果我尝试构建，我会得到“找到：解析。需要：parsing.parseresult [b]“ for tailRecm（a）（fn）

我可以说的是，我的类型<我的类型<， 代码>解析器[A] 是函数类型，而不仅仅是值类型？我试图通过修改tailRecm递归调用tailRecm（a）（fn）（input）（输入）来改善问题，但显然这也不是安全的，并且也不会安全，并且也不会安全。编译。

我该如何解决这个问题，更广泛地解决一般的功能类型的单调类型？

Answer 1

不可能使tailRecm本身本身进行尾声；您需要定义一个尾部回复辅助方法

，这是cats library实现tailRecm的function> function1

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

这是因为monadic递归是< em>相互访问，其中两种方法互相呼唤。 Scala编译器无法优化。因此，我们将其嵌入式元素定义，而不是调用flatmap或其他方法

Answer 2

您需要再次将输入再次传递到tailRecm呼叫

tailRecM(a)(fn)(input)

，因为tailRecm（a）（fn）（fn）返回parser ，但是您需要从该返回的Parser中的parserresult，就像您在所有其他情况下一样。