Tuple types

Robert James wrote:
> Is there any way in Scala's type system to make a func that takes an
> n-tuple and a m-tuple and returns a (n+m)-tuple?

Yes, it's possible using a more generic model of a tuple, i.e. a list of
heterogeneously typed elements (sometimes called HList). MetaScala
contains an implementation of it:

http://svn.assembla.com/svn/metascala/src/metascala/HLists.scala

Some example code:

http://svn.assembla.com/svn/metascala/src/metascala/example/HListExample...

/Jesper Nordenberg

On 8/11/09, Jesper Nordenberg wrote:
> Robert James wrote:
>> Is there any way in Scala's type system to make a func that takes an
>> n-tuple and a m-tuple and returns a (n+m)-tuple?
>
> Yes, it's possible using a more generic model of a tuple, i.e. a list of
> heterogeneously typed elements (sometimes called HList). MetaScala
> contains an implementation of it:

Quite interesting... could you explain how that works? Am I correct
that it will staticly, strongly type, even in cases where the literal
values of n and m vary at runtime?

On Tue, Aug 11, 2009 at 08:55:14PM -0400, Robert James wrote:
> Date: Tue, 11 Aug 2009 20:55:14 -0400
> From: Robert James
> To: Jesper Nordenberg
> Cc: scala@listes.epfl.ch
> Subject: Re: [scala] Re: Tuple types
>
> On 8/11/09, Jesper Nordenberg wrote:
> > Robert James wrote:
> >> Is there any way in Scala's type system to make a func that takes an
> >> n-tuple and a m-tuple and returns a (n+m)-tuple?
> >
> > Yes, it's possible using a more generic model of a tuple, i.e. a list of
> > heterogeneously typed elements (sometimes called HList). MetaScala
> > contains an implementation of it:
>
> Quite interesting... could you explain how that works? Am I correct
> that it will staticly, strongly type, even in cases where the literal
> values of n and m vary at runtime?

The numbers that are used for the type parameters in these
calculations are represented as Church Numerals. Note how
the example does not use the simple number 6, but instead
uses _6, which is a symbol for a type that happens to
be a Church Encoding of the number 6. These values are
statically checked at compile time and can not vary at
run time. If you are willing to invest a bit of time, you
might try reading my post "Practical Church Numerals in Scala"

where I build up a type-safe Units package based largely on
Jesper's code.

--
Jim

Robert James wrote:
> On 8/11/09, Jesper Nordenberg wrote:
>> Robert James wrote:
>>> Is there any way in Scala's type system to make a func that takes an
>>> n-tuple and a m-tuple and returns a (n+m)-tuple?
>> Yes, it's possible using a more generic model of a tuple, i.e. a list of
>> heterogeneously typed elements (sometimes called HList). MetaScala
>> contains an implementation of it:
>
> Quite interesting... could you explain how that works?

The idea is that a tuple (T1, T2, ..., Tn) is represented by the type
HList[T1, HList[T2, ...., HList[Tn, HNil]...]] (which also can be
written T1 :: T2 :: ... :: Tn :: HNil using Scala's infix type
notation). Now the tuple methods can be defined using recursive implicit
parameters. The tricky part is representing the method return types as
Scala previously didn't allow type parameters to be inferred from
implicit parameters. It seems this has changed in 2.8 so it might be
time to update and simplify the implementation.

> Am I correct
> that it will staticly, strongly type, even in cases where the literal
> values of n and m vary at runtime?

Since it's a tuple it's length can't vary at runtime, if that was the
case you would use a normal list.

/Jesper Nordenberg

Jim McBeath wrote:
> The numbers that are used for the type parameters in these
> calculations are represented as Church Numerals. Note how
> the example does not use the simple number 6, but instead
> uses _6, which is a symbol for a type that happens to
> be a Church Encoding of the number 6. These values are
> statically checked at compile time and can not vary at
> run time. If you are willing to invest a bit of time, you
> might try reading my post "Practical Church Numerals in Scala"
>
> where I build up a type-safe Units package based largely on
> Jesper's code.

That's a good description of the approach. Your blog should be added to
Planet Scala so more people find it.

/Jesper Nordenberg

On 8/12/09, Jesper Nordenberg wrote:
> > Am I correct
>> that it will staticly, strongly type, even in cases where the literal
>> values of n and m vary at runtime?
>
> Since it's a tuple it's length can't vary at runtime, if that was the
> case you would use a normal list.

Let's look at a method which takes tuple of type (A, B, C...) and of
type (X, Y, Z...) and makes a tuple of type (A,B,C,...X,Y,Z...).
Although the method on different calls will return different length
tuples, we can always statically infer the length of the tuple (given
the type of the arguments). We can't use lists, because the tuples
are heterogenously typed. And, we don't need lists, because we can
compute the length and type of the returned tuple, given the argument
tuples.

It boils down to the problem that Scala sees no connection between a
1-tuple and a 2-tuple and a 3-tuple - they're not all instances of
Tuple[T][n] or something like that. My question is if they'res any
expansion - in Scala or theory - to add this dimension.

Robert James wrote:
> Let's look at a method which takes tuple of type (A, B, C...) and of
> type (X, Y, Z...) and makes a tuple of type (A,B,C,...X,Y,Z...).
> Although the method on different calls will return different length
> tuples, we can always statically infer the length of the tuple (given
> the type of the arguments). We can't use lists, because the tuples
> are heterogenously typed. And, we don't need lists, because we can
> compute the length and type of the returned tuple, given the argument
> tuples.

This is exactly what the HList.::: method in MetaScala does. It can
concatenate tuples of arbitrary lengths and element types. Note that the
lengths and element types of the tuples are always known at compile time
in contrast to a list where these properties are often only known at
runtime. I don't know what other concept you're looking for.

/Jesper Nordenberg

I have been playing around with this problem also. My approach was to
ditch Tuples and focus on traits instead.

Landing at this

trait IRecord extends PartialFunction[Symbol,Any] with
Iterable[(Symbol,Any)]
{
def domain:Set[Symbol]
def get(s:Symbol):Option[Any]
def isDefinedAt(s:Symbol) = get(s).isDefined
def apply(s:Symbol) = get(s).getOrElse(error("Not defined for
" + s.name))
def elements = domain.map(s => (s,this(s))).elements
override def toString = "("+elements.map(t =>
t._1.name+"="+t._2).reduceLeft(_+","+_)+")"
}

trait ReflectiveRecord {
def get(s:Symbol) = try {
Some(getClass.getDeclaredMethod(s.name, null).invoke(this)) } catch {
case _ => None }
def domain = immutable.Set() ++
getClass.getDeclaredMethods.map((m:Method) => Symbol(m.getName))
}

abstract class Record extends IRecord with ReflectiveRecord

My though was to use it like

val r1 = new Record {
val a = "A"
val b = 12
}

val r2 = new Record {
val b = 13
val c = "C"
}

And define join like:

def +[R1<:IRecord,R2<:IRecord](r1:R1,r2:R2):R1 with R2

My hope was to use dynamic proxy to implement the R1 with R2 type, but
unfortunatlely even with dynamic proxy it would require some runtime
code generation.

BR,
John

On Wed, Aug 12, 2009 at 1:42 AM, Robert James wrote:
> Is there any way in Scala's type system to make a func that takes an
> n-tuple and a m-tuple and returns a (n+m)-tuple?
>
> I came into this issue when thinking about implementing relational
> algebra ops in Scala (think cross product of two relations).
>
> Is there any research about expanding type theories to cover cases like this?
>
> A related issue is the need to specify a size as part of the type:
> Function1, Function2.  There's a clear need for a basic set of
> operators on types, so we can say something like Function(N).  This
> would solve the above problem as well:
>  def meth(a: A(x), b: B(y)) : r: R(x+y)
>
> Any work on this, in Scala or elsewhere?
>