CODEWITHSUNDEEP
scalatypes
Simonlbc
Simonlbc

Reputation: 651

Recursive type for tuple like type

I'm trying to define a method ConcatToList would be able to convert some objects of type T~T or T~T~T or T~T~T~T or ... to a List[T].

My problem comes with how I should go about defining the type of ConcatToList

def ConcatToList[T](concat: ~[T, ???]) = ...

what should I replace ??? by ?

Upvotes: 2

Views: 179

Answers (2)

Archeg
Archeg

Reputation: 8462

The next code works for lists of mixed types:

  case class ~~[T, G](l: T, r: G)

  def concat[T, G](v: ~~[T, G]): List[T] = (v.l, v.r) match {
    case (left, right : ~~[T, _]) => left :: concat(right)
    case (left, right: T) => List(left, right)
  }

  println(concat(~~(2, 3)))                   // List(2, 3)
  println(concat(~~(2, ~~(4, 5))))            // List(2, 4, 5)
  println(concat(~~(2, ~~(4, ~~(5, 6)))))     // List(2, 4, 5, 6)
  println(concat(~~(2, ~~("s", 3.3))))        // List(2, s, 3.3)

  // but
  println(concat(~~(~~("s", 3.3), 2)))        // List(~~(s, 3.3), 2)

P.S. I will leave this as an example of simple approach, but see Travis response for a better type-safer way

Upvotes: 0

Travis Brown
Travis Brown

Reputation: 139058

I'll assume a representation like this:

class ~[I, L](val init: I, val last: L)

That you instantiate like this:

scala> val x: Int ~ Int ~ Int ~ Int = new ~(new ~(new ~(1, 2), 3), 4)
x: ~[~[~[Int,Int],Int],Int] = $tilde@3e6fa38a

You're not going to be able to write your ConcatToList method with a signature of the form you suggest, since there's no way to write a type constraint that describes exactly the types for which this operation is valid. Instead you can use a type class:

trait TildeToList[T] {
  type Elem
  def apply(t: T): List[Elem]
}

object TildeToList {
  type Aux[T, E] = TildeToList[T] { type Elem = E }

  implicit def baseTildeToList[E]: Aux[E ~ E, E] = new TildeToList[E ~ E] {
    type Elem = E
    def apply(t: E ~ E): List[E] = List(t.init, t.last)
  }

  implicit def recTildeToList[I, L](implicit ttl: Aux[I, L]): Aux[I ~ L, L] =
    new TildeToList[I ~ L] {
      type Elem = L
      def apply(t: I ~ L): List[L] = ttl(t.init) :+ t.last
    }
}

And then:

def tildeToList[T](t: T)(implicit ttl: TildeToList[T]): List[ttl.Elem] = ttl(t)

Which works like this:

scala> tildeToList(x)
res0: List[Int] = List(1, 2, 3, 4)

Note that what we get back is appropriately statically typed.

If you try to use it on a value that doesn't have an appropriate shape, you'll get a compile-time error:

scala> tildeToList(new ~('a, "a"))
<console>:16: error: could not find implicit value for parameter ttl: TildeToList[~[Symbol,String]]
       tildeToList(new ~('a, "a"))
                  ^

Which is presumably what you want.

Upvotes: 4

Related Questions