Polyvariadic joins in tagless final. Executable in a recent Scala REPL.

tagless_joins.scala

import scala.language.higherKinds

//Module signatures become traits/interfaces
trait Symantics {
    type Ctx[A]
    type Var[A]
    type Repr[A]
    type Shape[A]

    def from[A](shape: Repr[Shape[A]]): Var[Repr[A]]
    val cnil: Ctx[Unit]
    def ccons[A,B](v: Var[A], ctx: Ctx[B]): Ctx[(A,B)]

    def join[A,B](ctx: Ctx[A])(pattern: A => Repr[Shape[B]]): Repr[Shape[B]]

    def yld[A](x: Repr[A]): Repr[Shape[A]]
    def pair[A,B](fst: Repr[A], snd: Repr[B]): Repr[(A,B)]
  }

//For testing, extend the language with a syntax to lift lists of values to shape representations
trait SymanticsPlus extends Symantics {
   //note: A* means "variable number of A arguments"
   def lift[A](xs: A*): Repr[Shape[A]]
}

//Expression functors become functions/methods with path-dependent types
def test(s: SymanticsPlus) //infers path-dependent type s.Repr[s.Shape[(Double, (Int, String))]]
= {
  import s._
  //Note: with more effort, the syntax for constructing contexts can be made prettier, in infix notation
  val ctx = ccons(from(lift(1,2,3)), ccons(from(lift("one", "two")), ccons(from(lift(3.0,2.0,1.0)), cnil)))
  //Notational convenience is similar to the OCaml version
  join (ctx) { case (x,(y,(z,()))) =>
     yld(pair(z,pair(x,y)))
  }
  /* this wouldn't type check:
   join (ctx) { case (x,(y,())) =>
     yld(pair(z,pair(x,y)))
   }
   */
}

//Example: sequential cartesian product over lists
object ListSymantics extends SymanticsPlus {

  //GADT becomes class hierarchy
  sealed abstract class Ctx[A]
  //GADT constructors become case classes/objects
  case object CNil extends Ctx[Unit]
  case class CCons[A,B](hd: Var[A], tl: Ctx[B]) extends Ctx[(A,B)] //refinement controlled by extends clause

  sealed abstract class Var[A]
  case class Bind[A](shape: Repr[Shape[A]]) extends Var[Repr[A]]

  override type Repr[A] = A
  override type Shape[A] = List[A]

  override def from[A](shape: Repr[Shape[A]]) = Bind(shape)

  override val cnil = CNil

  override def ccons[A, B](v: Var[A], ctx: Ctx[B]) = CCons(v,ctx)

  override def lift[A](xs: A*) = List(xs:_*)

  override def yld[A](x: Repr[A]) = List(x)

  override def pair[A, B](fst: Repr[A], snd: Repr[B]) = (fst,snd)

  /* This join implements the monadic sequential semantics */  
  override def join[A, B](ctx: Ctx[A])(pattern: A => Repr[Shape[B]]) = ctx match {
    case CNil => pattern ()
    case CCons(Bind(xs), tl) =>
      xs.flatMap { x =>
        join (tl) { tuple => pattern (x,tuple) }
      }
  }
}

test(ListSymantics)
/* prints res0: ListSymantics.Repr[ListSymantics.Shape[(Double, (Int, String))]] =
List((3.0,(1,one)), (2.0,(1,one)), (1.0,(1,one)), (3.0,(1,two)), (2.0,(1,two)),
(1.0,(1,two)), (3.0,(2,one)), (2.0,(2,one)), (1.0,(2,one)), (3.0,(2,two)),
(2.0,(2,two)), (1.0,(2,two)), (3.0,(3,one)), (2.0,(3,one)), (1.0,(3,one)),
(3.0,(3,two)), (2.0,(3,two)), (1.0,(3,two))) */