Remove casts from the implementation of `Apply#tupled`

[mpilquist]

The tupled operation converts a (F[X1], F[X2], ...) to a F[(X1, X2, ...)] using map and map2. The current implementation iterates over the tuple in an untyped fashion, casting each element to F[Any], creating a F[(Any, Any, ...)] and finally casting back to F[(X1, X2, ...)]. It would be nice to have a version of this operation that didn't use any casts internally.

https://github.com/typelevel/spotted-leopards/blob/5a11b9b36ed701d395022f047fe7b665259a7f57/core/shared/src/main/scala/leopards/Apply.scala#L31-L35

I've spent a bunch of hours on this and seem to be stuck. Would appreciate any pointers, perhaps from @nicolasstucki or @milessabin.

[nicolasstucki]

To achieve this without casts you would probably need to make tupled inline and handle one element at a time.

Maybe try with a signature like this:

extension [H, T <: Tuple](t: F[H] *: T)(using Tuple.IsMappedBy[F][T])
  inline def tupled: F[H *: Tuple.InverseMap[T, F]] =
    ...

[mpilquist]

Thanks for the hint! If anyone wants to work on this, you can use this scala-cli script instead of working on this repo:

// using scala 3.1.1-RC1

import scala.compiletime.*
import Tuple.*

trait Apply[F[_]]:
  extension [A](fa: F[A])
    def map[B](f: A => B): F[B]
    def map2[B, C](fb: F[B])(f: (A, B) => C): F[C]

  inline def tupled[H, T <: Tuple](t: F[H] *: T)(using IsMappedBy[F][T]): F[H *: InverseMap[T, F]] =
    ???

given optApply: Apply[Option] with
  extension [A](fa: Option[A])
    def map[B](f: A => B) = fa.map(f)
    def map2[B, C](fb: Option[B])(f: (A, B) => C) =
      fa.flatMap(a => fb.map(b => f(a, b)))

@main def demo =
  println(optApply.tupled((Option(1), Option(2))))

This is as close as I got, but it's still using a bunch casts:

  inline def tupled[H, T <: Tuple](t: F[H] *: T)(using IsMappedBy[F][T]): F[H *: InverseMap[T, F]] =
    inline erasedValue[T] match
      case _: EmptyTuple => t.head.map(_ *: EmptyTuple).asInstanceOf[F[H *: InverseMap[T, F]]]
      case _: (F[h2] *: t2) =>
        val force = summon[Int =:= Int].asInstanceOf[IsMappedBy[F][t2]]
        val tail = t.tail.asInstanceOf[F[h2] *: t2]
        val tupledTail: F[InverseMap[T, F]] = tupled[h2, t2](tail)(using force).asInstanceOf[F[InverseMap[T, F]]]
        t.head.map2(tupledTail)(_ *: _)

[nicolasstucki]

Might also try

inline t match
  case t: F[H] *: EmptyTuple => ...
  case t: (F[H] *: F[h2] *: t2) => ...

[ncreep]

Hi,

Joining somewhat late to this discussion. But in case there's still interest in this issue, I've been experimenting with match-types lately, and managed to get something working without (runtime) casts.

The key idea that makes the compiler cooperate is to create match-types that follow the structure of the code. You can see that in the Tupled and MapCons types below.

The code does perform some "compile-time casting", but these are cosmetic, and can be avoided at the cost of making some type-signatures uglier.

Here's a scala-cli script with the implementation:

//> using scala "3.2.2"

import scala.compiletime.*
import Tuple.*
import scala.NonEmptyTuple

// asserting at compile-time that a tuple is non-empty
type NonEmpty[T <: NonEmptyTuple] <: NonEmptyTuple = T match
  case NonEmptyTuple => T

// asserting at compile-time that a given type is a tuple type
type IsTuple[T <: Tuple] <: Tuple = T match
  case T => T

trait Apply[F[_]]:
  extension [A](fa: F[A])
    def map[B](f: A => B): F[B]
    def map2[B, C](fb: F[B])(f: (A, B) => C): F[C]

  // In an ideal world we would use `Map[T, F]` here, but type-inference on the client side is not 
  // smart enough for this to work
  // If we use just `T` we will have clashes between the extensions for different implementations of `F[_]` 
  // wrappers
  // Adding `IsMappedBy` lets us disambiguate the different `F`s, while still maintaining type-inference
  // (apparently type-inference for implicits works better)
  extension [T <: NonEmptyTuple](tuple: T)(using IsMappedBy[F][T])
    inline def mapN[B](f: InverseMap[T, F] => B): F[B] =
      tuple.tupled.map(f)

    inline def tupled: F[InverseMap[T, F]] =
      // "casting" (at compile-time) so that we get a nicer return type for the client facing function
      inline tupledGeneric(tuple) match
        case result: F[InverseMap[T, F]] => result
  end extension

  private type Tupled[T <: NonEmptyTuple] = T match
    case F[h] *: EmptyTuple => F[h *: EmptyTuple]
    case F[h] *: NonEmpty[t] => MapCons[h, Tupled[t]]

  private type MapCons[H, FT] = FT match
    case F[IsTuple[t]] => F[H *: IsTuple[t]]

  private inline def tupledGeneric[T <: NonEmptyTuple](tuple: T): Tupled[T] =
    inline tuple match
      case t: (F[h] *: EmptyTuple) => t.head.map(_ *: EmptyTuple)
      case t: (F[h] *: NonEmpty[t]) => mapCons(t.head, tupledGeneric(t.tail))

  private inline def mapCons[H, T](h: F[H], t: T): MapCons[H, T] =
    inline t match
      case tail: F[IsTuple[t]] => h.map2(tail)(_ *: _)
end Apply

given optApply: Apply[Option] with
  extension [A](fa: Option[A])
    def map[B](f: A => B) = fa.map(f)
    def map2[B, C](fb: Option[B])(f: (A, B) => C) =
      fa.flatMap(a => fb.map(b => f(a, b)))

given listApply: Apply[List] with
  extension [A](fa: List[A])
    def map[B](f: A => B) = fa.map(f)
    def map2[B, C](fb: List[B])(f: (A, B) => C) =
      fa.flatMap(a => fb.map(b => f(a, b)))

@main def demo =
  val optTuple = (Option(1), Option(2), Option(3))
  val listTuple = (List(1), List(2), List(3))

  println(optTuple.tupled)
  println(optTuple.mapN(_ + _ + _))

  println(listTuple.tupled)
  println(listTuple.mapN(_ + _ + _))

[ncreep]

I'll keep on writing into the ether...

I noticed that I was using all those complicated match types just to circumvent the fact that I need GADT-like pattern matching. That is, I needed to unify a type-parameter with the specific type assignment that I get in a case branch. This would allow me to directly pattern-match on Tuple.Map[T, F] values and recurse on them.

But I found a cleaner way to get the compiler to provide me with this kind of unification: wrapping the scrutinee in a class with the type-parameter I'm matching on (the IsMap class in the snippet below). No idea why this works for unification, but it greatly simplifies the code, and completely removes any kind of casts (including compile-time ones).

//> using scala "3.3.1"

import scala.compiletime.*
import Tuple.*
import scala.NonEmptyTuple

trait Apply[F[_]]:
  extension [A](fa: F[A])
    def map[B](f: A => B): F[B]
    def map2[B, C](fb: F[B])(f: (A, B) => C): F[C]

  // In an ideal world we would use `Map[T, F]` here, but type-inference on the client side is not 
  // smart enough for this to work
  // If we use just `T` we will have clashes between the extensions for different implementations of `F[_]` 
  // wrappers
  // Adding `IsMappedBy` lets us disambiguate the different `F`s, while still maintaining type-inference
  // (apparently type-inference for implicits works better)
  extension [T <: NonEmptyTuple](tuple: T)(using toMap: IsMappedBy[F][T])
    inline def mapN[B](f: InverseMap[T, F] => B): F[B] =
      tuple.tupled.map(f)

    inline def tupled: F[InverseMap[T, F]] =
      tupledGeneric(toMap(tuple))
  end extension

  // a helper for pattern-matching, this lets us unify type variables in a `def` with
  // the variables in pattern-match cases
  case class IsMap[T <: Tuple](value: Map[T, F])

  // we can't propagate the `T <: NonEmptyTuple` constraint here because the `IsMappedBy`
  // implicit doesn't preserve it
  private inline def tupledGeneric[T <: Tuple](tuple: Map[T, F]): F[T] =
    inline IsMap(tuple) match
      case t: IsMap[h *: EmptyTuple] => t.value.head.map(_ *: EmptyTuple)
      case t: IsMap[h *: t] => 
        val head =  t.value.head
        val tail = tupledGeneric(t.value.tail)

        head.map2(tail)(_ *: _)
end Apply

given optApply: Apply[Option] with
  extension [A](fa: Option[A])
    def map[B](f: A => B) = fa.map(f)
    def map2[B, C](fb: Option[B])(f: (A, B) => C) =
      fa.flatMap(a => fb.map(b => f(a, b)))

given listApply: Apply[List] with
  extension [A](fa: List[A])
    def map[B](f: A => B) = fa.map(f)
    def map2[B, C](fb: List[B])(f: (A, B) => C) =
      fa.flatMap(a => fb.map(b => f(a, b)))

@main def demo =
  val optTuple = (Option(1), Option(2), Option(3))
  val listTuple = (List(1), List(2), List(3))

  println(optTuple.tupled)
  println(optTuple.mapN(_ + _ + _))

  println(listTuple.tupled)
  println(listTuple.mapN(_ + _ + _))

[mpilquist]

This is brilliant!

[mpilquist]

Closed via #19

[ncreep]

Cool, glad you found that snippet useful.