How do you deal with tuples of higher-order types?

Question

Scala 3, obviously. Scala 2's Tuple set-up would have kept me from trying this.

I'm trying to write a generic parser library with pluggable algorithms. So, when you write your grammar, it gets converted into an abstract syntax tree, and then those abstract syntax trees get fed to whichever algorithm you want to use, and the algorithm decides how it's going to parse the input.

So, for example, I have these data classes that all extend ParseExpr[+T]:

case class Term[T](t: T) extends ParseExpr[T] // a single terminal
case class NonTerm[T](name: String) extends ParseExpr[T] // a non-terminal
      // I also store the type of the non-terminal, but it's ugly

case class Alt[T](ps: List[Pexpr[T]]) extends ParseExpr[T] // a list of alternate ParseExprs
case class Cat[?](ps: ?) extends ParseExpr[?] // a sequence of ParseExprs

Everything works fine except the last one. The way that Scala parser combinators deals with the equivalent Alt and Cat is that it binarizes them. In other words, you can only have two ParseExprs inside Alt or Cat, but these could also be Alt and Cat, so you can build up the equivalent of p ~ q ~ r with Cat(Cat(p, q), r).

I'm implementing an algorithm that is much speedier when the parser is not binarized, so I'm trying to create a version of Cat that takes any number of ParseExprs. The problem, of course, is the the result of a sequence of parsers is a (heterogeneous) sequence of values. So I thought I could make things completely general and use the new Scala 3 Tuple.

Here's what I tried:

case class Cat[Ts <: Tuple](ps: Map[Ts, ParseExpr]) extends ParseExpr[Ts]

What I think this says is that Cat takes a tuple of ParseExprs, each with its own type, and produces a tuple of the given types in order. This is great. Except I can't do anything with it.

First, I have to convert a Cat[Ts](pes: Map[Ts, ParseExpr]) into an actual parser. To do that, I have to convert each ParseExpr into a Parser. So I tried to map over the Tuple:

parseExpr match
  case Cat(ps) => ps.map([t] => (pe: t) => parserFor(pe)) // should return Map[Ps, Parser]

But no matter how I do this, I can't get things to type-check.

Have I bitten off more than I can chew, and Tuples of higher-order types are just more trouble than they're worth, or am I missing something basic here?

---

Edit: After Dmytro rightly complained about my not providing code, I've banged away at this for the past couple of days, and I'm still stuck. What Dmytro provided does compile, but as soon as I try to write the actual parser, I get stuck. Here's what I have (also in scastie:

import scala.language.implicitConversions
import scala.Tuple.{Head, Tail, Map => TMap}

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]
case class Cat[Ps <: Tuple](ps: TMap[Ps, Pexpr]) extends Pexpr[Ps]

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

/* I tried to fake my own Tuple.Map with a wrapper, but couldn't
figure out how to write the map method.

trait TMap[Ts <: Tuple, M[_]]:
  type Out <: Tuple
  val instances: Out

object TMap:
  given[M[_]]: TMap[EmptyTuple, M] with
    type Out = EmptyTuple
    val instances = EmptyTuple

  given[M[_], H, T <: Tuple](using head: M[H], mt: TMap[T, M]): TMap[H *: T, M] with
    type Out = M[H] *: mt.Out
    val instances = head *: mt.instances
*/
type ParserFor[P <: Pexpr[?]] <: Parser[?] = P match
  case Pexpr[p] => Parser[p]

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

def catHelper[Ps <: Tuple](pexprs: TMap[Ps, Pexpr])(
  using TMap[TMap[Ps, Pexpr], ParserFor] =:= TMap[Ps, Parser]
): Parser[Ps] = 
  val parsers: TMap[Ps, Parser] = pexprs.map[ParserFor]([p] => (pexpr: p) => pexpr match
    case pe: Pexpr[p] => parserFor[p](pe)
  )
  cat(parsers)

def elem(t: Char): Parser[Char] = new Parser[Char] { 
  def apply(input: InputPos): Result[Char] =
    if (input.charAt == t) Success(t, input.next)
    else Failure(s"expected $t, found ${input.charAt}", input)  
}

def cat[Ps <: Tuple](ps: TMap[Ps, Parser]): Parser[Ps] = ps match
  case _: EmptyTuple => new Parser[Ps] { 
    def apply(input: InputPos): Result[Ps] = Success[Ps](Tuple(), input)
  }
  case (h: Parser[Head[Ps]]) *: (t: TMap[Tail[Ps], Parser]) => new Parser[Ps] { 
    def apply(input: InputPos): Result[Ps] = h.apply(input) match
      case Success(first, inputNext) => 
        cat(t).apply(inputNext).map((rest: Tail[Ps]) => first *: rest)
      case f@Failure(msg, inputNext) => f
  }

In the middle is where I tried a trick from one of the links Dmytro provided, but then I had to write a map method on a TMap[Tup, M[_]] and got lost.

Any help greatly appreciated!

Answer 1

If you start to perform type-level calculations with HLists aka Tuples (operations on tuples like Tuple.Map are defined in terms of match types) you should keep using

• match types, or

• type classes.

You should be prepared that working with match types (especially on value level) can be tricky, there are many limitations, and type inference is quite weak

How to prove that `Tuple.Map[H *: T, F] =:= (F[H] *: Tuple.Map[T, F])` in Scala 3

Tuples in Scala 3 Compiler Operations for Typeclass Derivation

Type-level filtering tuple in Scala 3

How to get match type to work correctly in Scala 3

Scala 3: typed tuple zipping

scala 3 map tuple to futures of tuple types and back

Express function of arbitrary arity in vanilla Scala 3

Shapeless3 and annotations

Scala 3. Implementing Dependent Function Type

In Scala 3, how to replace General Type Projection that has been dropped?

What does Dotty offer to replace type projections?

But no matter how I do this, I can't get things to type-check.

I'm afraid this is not a proper description of what you're doing and what errors you get. You should always prepare MCVE and then we can consider your specific compile errors. Also you should supplement MCVE with sample inputs and desirable outputs.

The following code seems to compile

trait Parser[T]

sealed trait ParseExpr[T]
case class Term[T](t: T) extends ParseExpr[T]
case class NonTerm[T](name: String) extends ParseExpr[T]
case class Alt[T](ps: List[ParseExpr[T]]) extends ParseExpr[T]
case class Cat[Ts <: Tuple](ps: Tuple.Map[Ts, ParseExpr]) extends ParseExpr[Ts]

def parserFor[T](pe: ParseExpr[T]): /*ParserFor[T]*/Parser[T] = ???

type ParserFor[T /*<: ParseExpr[?]*/] /*<: Parser[?]*/ = T match
  case ParseExpr[t] => Parser[t]

type Ps <: Tuple
val parseExpr: ParseExpr[Ps] = ???
val res = parseExpr match
  case Cat(ps) => ps.map[ParserFor]([pe_t /*<: ParseExpr[?]*/] => (pe: pe_t) => pe match
    case pe: ParseExpr[t] => parserFor[t](pe)
  )

def test(using Tuple.Map[Tuple.Map[Ps, ParseExpr], ParserFor] =:= Tuple.Map[Ps, Parser]): Unit =
  res: Tuple.Map[Ps, Parser]

Scala 3.2.2