type level pattern matching in scala

Question

Ideally I'd like to write Haskell style pattern matching on the type level in Scala, something like this:

Can shapeless be used for something like this ?

object Test{


  type F[Int] = String
  type F[Boolean] = Int  // but this line does not compile

  implicitly[String =:= F[Int]]
  implicitly[Int =:= F[Boolean]]

}

In this example if F takes Int then it returns String and if it takes Boolean then it returns Int.

Clarification (based on this answer)

Here is how I'd like to use these types in functions and typeclasses:

  abstract class WrappedF[T] {
    type F
    type Unwrap = T
  }

  type F[X <: WrappedF[_]] = X#F

  class IntF      extends WrappedF[Int]     { type F = StringF }
  class BooleanF  extends WrappedF[Boolean] { type F = IntF }
  class StringF   extends WrappedF[String]  { type F = Nothing }

  implicitly[String =:= F[IntF]#Unwrap]
  implicitly[Int =:=    F[BooleanF]#Unwrap]
  implicitly[String =:= F[F[BooleanF]]#Unwrap]

  // this is a type class definition where `V` is a member of the `Test` class
  // `f`'s type should be defined by `V`, but it does not work :(


  trait Test[V <: WrappedF[V]]{
    def f(a: F[V]#Unwrap): F[V]#Unwrap // this does not compile
  }

  implicit object TestImpl extends Test[IntF]{
    override def f(a: F[IntF]#Unwrap): F[IntF]#Unwrap = {
      val z: F[IntF]#Unwrap = "fd"+a
      z
    }
  }

Answer 1

Here two non-shapeless solutions.

1. A little type-level table of constants with funny names:

   type F = {
     type Int = java.lang.String
     type Boolean = scala.Int
   }
   
   implicitly[String =:= F#Int]
   implicitly[Int =:= F#Boolean]
   

   Here, F is a type with two type members that have names Int and Boolean (could be I and B, those two constants aren't really connected with Int or Boolean in any way). This doesn't compose: you can't write down something like F#F#Int.

2. You can lift every type T for which you want to define F into a type that has both T and F[T] as type members:

   abstract class WrappedF[T] {
     type F
     type Unwrap = T
   }
   type F[X <: WrappedF[_]] = X#F
   class IntF extends WrappedF[Int] { type F = StringF }
   class BooleanF extends WrappedF[Boolean] { type F = IntF }
   class StringF extends WrappedF[String] { type F = Nothing }
   
   implicitly[String =:= F[IntF]#Unwrap]
   implicitly[Int =:= F[BooleanF]#Unwrap]
   implicitly[String =:= F[F[BooleanF]]#Unwrap]
   

   This adds more noise because of ...F and #Unwrap, but is purely a type-level computation, and it composes (as the last example shows).

---

Update (better suited for abstracting over V <: WrappedF)

In your code under "Clarification", you were missing F <: WrappedF bound on the type member F:

  abstract class WrappedF {
    type F <: WrappedF
    type Unwrap
  }

  type F[X <: WrappedF] = X#F

  class IntF      extends WrappedF { type Unwrap = Int;     type F = StringF }
  class BooleanF  extends WrappedF { type Unwrap = Boolean; type F = IntF }
  class StringF   extends WrappedF { type Unwrap = String;  type F = Nothing }

  implicitly[String =:= F[IntF]#Unwrap]
  implicitly[Int    =:= F[BooleanF]#Unwrap]
  implicitly[String =:= F[F[BooleanF]]#Unwrap]

  trait Test[V <: WrappedF]{
    def f(a: F[V]#Unwrap): F[V]#Unwrap // this does not compile
  }

  implicit object TestImpl extends Test[IntF] {
    override def f(a: String): String = {
      val z: F[IntF]#Unwrap = "fd" + a
      z
    }
  }

Answer 2

You use a typeclass style implicit structure with a type member.

// sealed for closed family
class F[I] { type O }
object F {
  type Rel[I, O0] = F[I] { type O = O0 }
  /* private */ def mkF[I, O0]: Rel[I, O0] = new F[I] { override type O = O0 }
  implicit val fInt: Rel[Int, String] = mkF
  implicit val fBoolean: Rel[Boolean, Int] = mkF
  def apply[I](implicit f: F[I]): f.type = f // f.type survives the refinement (see what breaks on removal)
}

locally { val temp = F[Int]; implicitly[temp.O =:= String] }
locally { val temp = F[Boolean]; implicitly[temp.O =:= Int] }
locally { val temp0 = F[Boolean]; val temp1 = F[temp0.O]; implicitly[temp1.O =:= String] }