Scala 3高阶元组在通用解析器库中的类型适配问题求助

你尝试用Scala 3的Tuple实现支持任意数量解析表达式的Cat，替代传统二元化的解析器组合子以提升算法性能，但在将Cat中的Pexpr元组转换为Parser元组时，始终无法通过类型检查，尤其是TMap的map方法实现陷入困境。

关键问题点 #

• Cat的类型定义错误：误用TMap[Ps, Pexpr]作为ps的类型，TMap是Tuple的类型操作（用于描述元组元素的类型映射），而非实际的元组类型。Cat的参数应该是元素均为Pexpr[?]的元组Ps <: Tuple。
• ParserFor类型别名的局限性：原类型别名无法正确推导Pexpr到Parser的类型映射，需要结合内联方法和Tuple的类型操作实现安全转换。
• 元组遍历的类型推导问题：直接使用TMap的map方法无法正确捕获每个Pexpr的具体类型，需要内联递归或类型类处理元组元素转换。

修复后的完整代码 #

import scala.Tuple.{Head, Tail, IsEmpty, Map => TupleMap}

case class InputPos(in: IndexedSeq[Char], pos: Int):
  def charAt: Char = in(pos)
  def next: InputPos = copy(pos = pos + 1)

trait Pexpr[+P]
case class Term(t: Char) extends Pexpr[Char]
// Cat接收元素为Pexpr[?]的元组，输出对应类型的元组
case class Cat[Ps <: Tuple](ps: Ps) extends Pexpr[Ps]
  // 约束元组每个元素都是Pexpr类型
  given [P, TailPs <: Tuple]: (Ps =:= Pexpr[P] *: TailPs) =:= (Pexpr[P] *: TailPs) = implicitly

trait Result[+P]:
  val next: InputPos
  def map[P2](f: P => P2): Result[P2]

case class Success[P](value: P, next: InputPos) extends Result[P]:
  def map[P2](f: P => P2): Result[P2] = copy(value = f(value))
case class Failure(msg: String, next: InputPos) extends Result[Nothing]:
  def map[P2](f: Nothing => P2): Result[P2] = this

trait Parser[+P] extends (InputPos => Result[P])

// 类型别名：映射Pexpr[p]到Parser[p]
type ParserFor[P] = P match
  case Pexpr[p] => Parser[p]

// 内联方法：将Pexpr元组转换为Parser元组
inline def pexprsToParsers[Ps <: Tuple](pexprs: Ps): TupleMap[Ps, ParserFor] =
  inline pexprs match
    case EmptyTuple => EmptyTuple
    case (head: Pexpr[p]) *: tail => parserFor(p)(head) *: pexprsToParsers(tail)

def parserFor[P](pexpr: Pexpr[P]): Parser[P] = pexpr match
  case Term(t) => elem(t)
  case Cat(pexprs) => cat(pexprsToParsers(pexprs))

def elem(t: Char): Parser[Char] = new Parser[Char]:
  def apply(input: InputPos): Result[Char] =
    if input.pos < input.in.length && input.charAt == t then
      Success(t, input.next)
    else
      Failure(s"expected '$t', found ${if input.pos < input.in.length then s"'${input.charAt}'" else "end of input"}", input)

// 递归实现多元素Parser元组的串联解析
def cat[Ps <: Tuple](parsers: TupleMap[Ps, ParserFor]): Parser[Ps] =
  inline parsers match
    case EmptyTuple => new Parser[EmptyTuple]:
      def apply(input: InputPos): Result[EmptyTuple] = Success(EmptyTuple, input)
    case (head: Parser[p]) *: (tail: TupleMap[TailPs, ParserFor]) =>
      new Parser[p *: TailPs]:
        def apply(input: InputPos): Result[p *: TailPs] =
          head(input) match
            case Success(headVal, nextPos) =>
              cat(tail)(nextPos).map(tailVal => headVal *: tailVal)
            case fail: Failure => fail

关键修复说明 #

1. 修正Cat的类型：Cat现在接收元组Ps，并通过上下文约束确保元组每个元素都是Pexpr类型，让类型推导正确关联输入和输出元组的类型。
2. 内联元组转换：使用inline方法pexprsToParsers结合模式匹配，递归遍历元组元素，将Pexpr[p]转换为Parser[p]，利用Scala 3内联特性实现编译期类型安全。
3. 简化ParserFor类型别名：直接匹配Pexpr[p]映射到Parser[p]，配合内联方法的类型推导，确保每个转换的类型正确性。
4. 递归cat函数：通过内联模式匹配处理空元组和非空元组的情况，递归串联解析器，将每个解析结果组合成对应元组。

调整后代码可正确通过类型检查，同时实现了非二元化的Cat解析表达式，满足性能优化需求。

内容的提问来源于Stack Exchange，提问作者Todd O'Bryan