Type lists and HArray

Cool! I experimented with this some time ago (http://code.google.com/p/kinded-scala/source/browse/trunk/examples/src/scala/examples/tcpoly/typecomp/tuples/tuples.scala), but never got the indexing to work :-(
nice work!adriaan

On Mon, Sep 14, 2009 at 2:48 PM, Jesper Nordenberg <megagurka@yahoo.com> wrote:

I've posted a blog entry about type lists in Scala. These can be used together with an array to implement a generic, type safe tuple class in a simple and, I believe, novel way. Link:

http://jnordenberg.blogspot.com/2009/09/type-lists-and-heterogeneously-typed.html

/Jesper Nordenberg


Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm

Yes, that looks very similar to what's available in MetaScala. Your
tuple implementation is basically the same as HList. HArray should
potentially be more efficient in many cases.

/Jesper Nordenberg

Adriaan Moors wrote:
> Cool! I experimented with this some time ago
> (http://code.google.com/p/kinded-scala/source/browse/trunk/examples/src/s...),
> but never got the indexing to work :-(
>
> nice work!
> adriaan
>
> On Mon, Sep 14, 2009 at 2:48 PM, Jesper Nordenberg > wrote:
>
> I've posted a blog entry about type lists in Scala. These can be
> used together with an array to implement a generic, type safe tuple
> class in a simple and, I believe, novel way. Link:
>
> http://jnordenberg.blogspot.com/2009/09/type-lists-and-heterogeneously-t...
>
> /Jesper Nordenberg
>
>
> Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm
>
>

On Mon, Sep 14, 2009 at 8:35 AM, Jesper Nordenberg <megagurka@yahoo.com> wrote:

Yes, that looks very similar to what's available in MetaScala. Your tuple implementation is basically the same as HList. HArray should potentially be more efficient in many cases.

I'm using Jesper's HList stuff in Goat Rodeo.  It's a huge win! 

/Jesper Nordenberg

Adriaan Moors wrote:

Cool! I experimented with this some time ago (http://code.google.com/p/kinded-scala/source/browse/trunk/examples/src/scala/examples/tcpoly/typecomp/tuples/tuples.scala), but never got the indexing to work :-(

nice work!
adriaan

On Mon, Sep 14, 2009 at 2:48 PM, Jesper Nordenberg <megagurka@yahoo.com <mailto:megagurka@yahoo.com>> wrote:

   I've posted a blog entry about type lists in Scala. These can be
   used together with an array to implement a generic, type safe tuple
   class in a simple and, I believe, novel way. Link:

   http://jnordenberg.blogspot.com/2009/09/type-lists-and-heterogeneously-typed.html

   /Jesper Nordenberg


   Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm

--
Lift, the simply functional web framework http://liftweb.net
Beginning Scala http://www.apress.com/book/view/1430219890
Follow me: http://twitter.com/dpp
Git some: http://github.com/dpp

I just noticed your type pattern matching example for Scala 3. I
understand it's a bit far fetched to think that it will be implemented
any time soon, but is there any chance of getting some form of type
equality check in Scala? Something like, type IfEq[T1, T2, IfTrue,
IfFalse] (implemented as "if (T1 == T2) IfTrue else IfFalse"). This is
sorely missed when writing type functions, and can only be worked around
in some cases using a visitor like pattern.

/Jesper Nordenberg

Adriaan Moors wrote:
> Cool! I experimented with this some time ago
> (http://code.google.com/p/kinded-scala/source/browse/trunk/examples/src/s...),
> but never got the indexing to work :-(
>
> nice work!
> adriaan
>
> On Mon, Sep 14, 2009 at 2:48 PM, Jesper Nordenberg > wrote:
>
> I've posted a blog entry about type lists in Scala. These can be
> used together with an array to implement a generic, type safe tuple
> class in a simple and, I believe, novel way. Link:
>
> http://jnordenberg.blogspot.com/2009/09/type-lists-and-heterogeneously-t...
>
> /Jesper Nordenberg
>
>
> Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm
>
>

On Mon, Sep 14, 2009 at 7:03 PM, Jesper Nordenberg <megagurka@yahoo.com> wrote:

I just noticed your type pattern matching example for Scala 3. I understand it's a bit far fetched to think that it will be implemented any time soon, but is there any chance of getting some form of type equality check in Scala? Something like, type IfEq[T1, T2, IfTrue, IfFalse] (implemented as "if (T1 == T2) IfTrue else IfFalse"). This is sorely missed when writing type functions, and can only be worked around in some cases using a visitor like pattern.

I agree, and I spent the last couple of days hacking the type checker to add EXPERIMENTAL (as in: this may never make it into trunk, not even hidden behind -Xexperimental) support for this. The commit is at http://github.com/adriaanm/scala/commit/16fbf8a10a0319f77c63baedd5ea40714c3c0ab8
This allows code like:
object Test {  sealed abstract class =:=[From, To] extends (From => To)  implicit def typeEquals[A]: A =:= A = new (A =:= A) {def apply(x: A) = x}
  sealed abstract class Test[Tst] {    type If[True, False]  }    case class FalseTest[Tst] extends Test[Tst] {    type If[True, False] = False   }    implicit def TrueTest[Tst](implicit witness: Tst) = new TrueTest[Tst]  class TrueTest[Tst](implicit val witness: Tst) extends Test[Tst] {    type If[True, False] = True    }    class If[C](implicit val witness: Test[C] = FalseTest[C]) {     type ThenElse[T, E] = witness.If[T, E]  }
  val x : If[Int =:= String]#ThenElse[Boolean, String] = "Test"   val y : If[Int =:= Int]#ThenElse[Boolean, String] = false}
The idea is that If[Int =:= Int]#ThenElse[Boolean, String] normalizes to If[Int =:= Int]#witness.type#If[Boolean, String], now If[Int =:= Int]#witness.type is statically known to be TrueTest[Int =:= Int] (by successful implicit search -- this is new),and TrueTest[Int =:= Int]#If[Boolean, String] normalizes to Boolean
Similarly, If[Int =:= String]#ThenElse[Boolean, String] normalizes to If[Int =:= String]#witness.type#If[Boolean, String],now If[Int =:= String]#witness.type is statically known to be FalseTest[Int =:= String] (by failure of implicit search and the default argument -- this is new),   and FalseTest[Int =:= String]#If[Boolean, String] normalizes to String
My implementation is not tested thoroughly, so bugfixes (or reports) welcome!  (I'd love to know whether more interesting conditions for the If work, for example..)
In the end this kind of type-level hacking is not ideal, so I may not integrate this and instead wait until we come up with a more robust/elegant approach...
cheers, adriaan

Adriaan Moors wrote:
> The idea is that If[Int =:= Int]#ThenElse[Boolean, String] normalizes
> to If[Int =:= Int]#witness.type#If[Boolean, String],
> now If[Int =:= Int]#witness.type is statically known to be TrueTest[Int
> =:= Int] (by successful implicit search -- this is new),
> and TrueTest[Int =:= Int]#If[Boolean, String] normalizes to Boolean

This feels a bit magical IMHO as it would introduce different typing
rules for implicit and explicit vals. For example this doesn't work in 2.8:

class A {type T}
class B(val a : A) {type T = a.T}
val b = new B(new A {type T = Int})
val i : b.T = 10 // Compiler error

but it works if you define B as:

class B[C <: A](val a : C) {type T = a.T}

So an alternative solution would be to enable partial application of
type parameters (which has been discussed before):

class TypeEq[T1, T2, R]
implicit def areEq[T] = new TypeEq[T, T, True]
class AreEq[T1, T2, R](implicit val w : TypeEq[T1, T2, R] = TypeEq[T1,
T2, False]) { type T = R }

// Note that type parameter R is left out and inferred by the compiler
// (syntax subject to discussion)
val t : AreEq[Int, Int]#T = True

I think partially applied type parameters would be handy in many other
situations as well.

/Jesper Nordenberg

On Fri, Sep 18, 2009 at 10:40 AM, Jesper Nordenberg <megagurka@yahoo.com> wrote:

Adriaan Moors wrote:
> The idea is that If[Int =:= Int]#ThenElse[Boolean, String] normalizes
> to If[Int =:= Int]#witness.type#If[Boolean, String],
> now If[Int =:= Int]#witness.type is statically known to be TrueTest[Int
> =:= Int] (by successful implicit search -- this is new),
> and TrueTest[Int =:= Int]#If[Boolean, String] normalizes to Boolean

This feels a bit magical IMHO as it would introduce different typing rules for implicit and explicit vals.

Well, they are intrinsically quite different, as implicit values are decided at compile time, whereas explicit ones are not. Since implicit values "live" in the same period as types, to me it makes sense to involve them (more closely) in the type checking process (note that they have already started to influence type inference to get the builders of the new collection library to work)   

So an alternative solution would be to enable partial application of type parameters (which has been discussed before):

class TypeEq[T1, T2, R]
implicit def areEq[T] = new TypeEq[T, T, True]
class AreEq[T1, T2, R](implicit val w : TypeEq[T1, T2, R] = TypeEq[T1, T2, False]) { type T = R }

// Note that type parameter R is left out and inferred by the compiler
// (syntax subject to discussion)
val t : AreEq[Int, Int]#T = True

I think partially applied type parameters would be handy in many other situations as well.

I agree. However, they are more complicated to implement. Nonetheless, they are definitely more likely to end up in post-2.8 Scala than what I hacked together (I still think that has potential too, but it needs to be explored more).
cheersadriaan

Adriaan Moors wrote:
> Well, they are intrinsically quite different, as implicit values are
> decided at compile time, whereas explicit ones are not. Since implicit
> values "live" in the same period as types, to me it makes sense to
> involve them (more closely) in the type checking process (note that they
> have already started to influence type inference to get the builders of
> the new collection library to work)

I'm still a bit confounded by this (probably due to my limited brain
capacity). Take the following example:

class A { type T }
implicit def ia = new A { type T = Int }
class B(implicit val a : A) { type T = a.T }

// This should work I presume
val b1 : B = new B

// Will this give a compiler error (B#T and b2.T are different types)?
val b2 : B = new B(new A { type T = Boolean })

How do we write the type of b2?

/Jesper Nordenberg

On Fri, Sep 18, 2009 at 2:15 PM, Jesper Nordenberg <megagurka@yahoo.com> wrote:

Adriaan Moors wrote:

Well, they are intrinsically quite different, as implicit values are decided at compile time, whereas explicit ones are not. Since implicit values "live" in the same period as types, to me it makes sense to involve them (more closely) in the type checking process (note that they have already started to influence type inference to get the builders of the new collection library to work)

I'm still a bit confounded by this (probably due to my limited brain capacity). Take the following example:

Jesper, I'm sorry to be the one to tell you this, but if you have a limited brain capacity, I'm braindead, k?
 

class A { type T }
implicit def ia = new A { type T = Int }
class B(implicit val a : A) { type T = a.T }

// This should work I presume
val b1 : B = new B

// Will this give a compiler error (B#T and b2.T are different types)?
val b2 : B = new B(new A { type T = Boolean })

How do we write the type of b2?

/Jesper Nordenberg

--
Viktor Klang

Blog: klangism.blogspot.com
Twttr: viktorklang

Lift Committer - liftweb.com
AKKA Committer - akkasource.org
Cassidy - github.com/viktorklang/Cassidy.git
SoftPub founder: http://groups.google.com/group/softpub

[moving to debate from user]

On Fri, Sep 18, 2009 at 2:15 PM, Jesper Nordenberg <megagurka@yahoo.com> wrote:

Adriaan Moors wrote:

Well, they are intrinsically quite different, as implicit values are decided at compile time, whereas explicit ones are not. Since implicit values "live" in the same period as types, to me it makes sense to involve them (more closely) in the type checking process (note that they have already started to influence type inference to get the builders of the new collection library to work)

I'm still a bit confounded by this (probably due to my limited brain capacity). Take the following example:

class A { type T }
implicit def ia = new A { type T = Int }
class B(implicit val a : A) { type T = a.T }

// This should work I presume
val b1 : B = new B

in principle, yes, but I don't think I call adaptType in all the right places to make this work (haven't tried -- working on my partial type application branch ;-))   

// Will this give a compiler error (B#T and b2.T are different types)?
val b2 : B = new B(new A { type T = Boolean })

in principle this would be an error (I haven't implemented that, since I hadn't thought of it yet -- good point!)
the RHS has type `B{type T=Boolean}`  (*) (from `B{type T=a.type#T}` where `a.type` gets widened to `A{type T = Boolean}` based on typing the constructor argument `new A { type T = Boolean}`  -- this is the bit that isn't implemented, I guess this is enough to convince me to drop the idea, as it's getting even hairier now)
(*) for simplicity, I glossed over the fact that you can't override the alias type in B, see below
the expected type for `b2` is `B{type T=Int}` (by the logic that is described in my original mail)  

How do we write the type of b2?

one approach would be to use an "existential value", which is already supported, in combination with allowing to specify constructor arguments in a type (not supported):   `B(x forSome {val x: A { type T = Boolean }})`, which could be abbreviated to `B(_ : A { type T = Boolean })`
That's pretty unwieldy, though, I admit... :-)
To me, the interesting part of this approach is that it shows how values and types play together. There are two ways to approach this dilemma: keep types and values strictly separated, as in Omega (Tim Sheard), or embrace the dependencies and provide language support for them (Scala, Coq).   In the end, we want to use types to govern the value level, so the latter approach seems more productive.  More concretely, I'm interested in exploring how implicit search and type inference relate, as they both infer entities, albeit at different levels (the former: values, the latter: types, obviously). How can we describe their interaction elegantly? How can our type-level hacking benefit from this interaction?
Thanks for your input!
cheers,adriaan

Adriaan Moors wrote:
> one approach would be to use an "existential value", which is already
> supported, in combination with allowing to specify constructor arguments
> in a type (not supported):
> `B(x forSome {val x: A { type T = Boolean }})`, which could be
> abbreviated to `B(_ : A { type T = Boolean })`

That would work, but I don't think it's very intuitive. When you write
"new B(...)" (and B has no type parameters), it's reasonable to expect
it to have type B.

> To me, the interesting part of this approach is that it shows how values
> and types play together. There are two ways to approach this dilemma:
> keep types and values strictly separated, as in Omega (Tim Sheard), or
> embrace the dependencies and provide language support for them (Scala,
> Coq). In the end, we want to use types to govern the value level, so
> the latter approach seems more productive.

I definitely think it's preferable to only work with types at the type
level. Creating implicit values and functions just to be able to infer a
type seems like a backwards and cumbersome way compared to:

- built-in type expressions: type F[T1, T2] = (T1 <: T2)#IfElse[Int,
Boolean]

- type specialization (a la C++): type F[T] = Boolean; type F[T <: Int]
= Float

- type implicits (and partial application): trait A[T1, T2] {type T =
T2}; implicit type IA = A[Int, Boolean]; type F[implicit T2 <: A[Int,
_]] = T2#T

And there's probably other solutions as well.

> More concretely, I'm
> interested in exploring how implicit search and type inference relate,
> as they both infer entities, albeit at different levels (the former:
> values, the latter: types, obviously). How can we describe their
> interaction elegantly? How can our type-level hacking benefit from this
> interaction?

I think the most important step was taken in 2.8 when type parameters
could be inferred from implicit parameters.

/Jesper Nordenberg

Fascinating discussion! I wish I could more actively contribute (must say I'm a bit out of my league here), but I was playing around with a type-level implementation of Conway games just the other day and both type equality checks and partial type application would have vastly simplified things.

Keenly following the developments.
- Colin

Dear Colin,
Now that sounds interesting! Is your code for type level Conway games web-accessible?
Best wishes,
--greg

On Fri, Sep 18, 2009 at 7:06 AM, Colin Bullock <cmbullock@gmail.com> wrote:

Fascinating discussion! I wish I could more actively contribute (must say I'm a bit out of my league here), but I was playing around with a type-level implementation of Conway games just the other day and both type equality checks and partial type application would have vastly simplified things.

Keenly following the developments.
- Colin

--
L.G. Meredith
Managing Partner
Biosimilarity LLC
1219 NW 83rd St
Seattle, WA 98117

+1 206.650.3740

http://biosimilarity.blogspot.com

Now that sounds interesting! Is your code for type level Conway games web-accessible?

Not currently. At this point, I have little more down in code than some experimenting around to see how far I could push things.

I'm definitely stretching the limits of my type-fu here (likely why it's so enjoyable), and have run up against a few walls related to cyclic type definitions and "conditional" types for defining ordering over games. I've also yet to find a satisfactory type to represent sets of positions in games so I've resorted to living with the restriction of only dealing with the greatest and least position for left and right respectively (which potentially seems acceptable for numbers, but likely not so for arbitrary games).

If I have some time to put into it, and can satisfy both the compiler and myself, I'd be happy to share what I've come up with on github or somewhere.

- Colin

Given this definition of function I haven't had any problem with partial evaluation:
    trait F {        type apply[_ <: F] <: F    }

On Fri, Sep 18, 2009 at 4:06 PM, Colin Bullock <cmbullock@gmail.com> wrote:

Fascinating discussion! I wish I could more actively contribute (must say I'm a bit out of my league here), but I was playing around with a type-level implementation of Conway games just the other day and both type equality checks and partial type application would have vastly simplified things.

Keenly following the developments.
- Colin

I was just writing some boilerplate code that could be removed if TupleX supported map/forall/... uniformly
I haven't thought deeply about whether it is possible, but my code looks like this:
  type ContainsBinder[T] = T => Nominal[T]
  trait Nominal[Self] {    def swap(a: Name, b: Name): Self    def fresh(a: Name): Boolean  }
  implicit def PairIsNominal[T : ContainsBinder, U: ContainsBinder] = (self: (T, U)) => new Nominal[(T, U)] {    def swap(a: Name, b: Name) = (self._1.swap(a, b), self._2.swap(a, b))      def fresh(a: Name) = self._1.fresh(a) && self._2.fresh(a)  }
Could your HList approach be used to generalise PairIsNominal to deal with all Tuples whose element types are context bound by ContainsBinder?

adriaan

On Mon, Sep 14, 2009 at 2:48 PM, Jesper Nordenberg <megagurka@yahoo.com> wrote:

I've posted a blog entry about type lists in Scala. These can be used together with an array to implement a generic, type safe tuple class in a simple and, I believe, novel way. Link:

http://jnordenberg.blogspot.com/2009/09/type-lists-and-heterogeneously-typed.html

/Jesper Nordenberg


Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm

Yes, if I understand your intention correctly, it's quite easy to write
map and fold functions for HList. They would have types (excluding
implicit parameters):

def map[L <: HList, I, O](l : L, fn : I => O) : List[O]
def foldLeft[L <: HList, T1, T2](l : L, v : T1, fn : (T1, T2) => T1) : T1

To this you would need to add implicit parameters to verify that I and
T2 are super types of all element types in the HLists. Here's a complete
example:

object HLists {
trait HList
class HNil extends HList
val HNil = new HNil()
case class HCons[H, T <: HList](head : H, tail : T) extends HList

case class Mapper[L <: HList, I, O](fn : (L, I => O) => List[O])
implicit def nilMapper[I, O] = Mapper[HNil, I, O]((l, fn) => Nil)

implicit def consMapper[H, T <: HList, I >: H, O](implicit m :
Mapper[T, I, O]) =
Mapper[HCons[H, T], I, O]((l, fn) => fn(l.head) :: m.fn(l.tail, fn))

def map[L <: HList, I, O](l : L, fn : I => O)(implicit m : Mapper[L,
I, O]) = m.fn(l, fn)

case class Folder[L <: HList, T1, T2](fn : (L, T1, (T1, T2) => T1) => T1)
implicit def nilFolder[T1, T2] = Folder[HNil, T1, T2]((l, v, fn) => v)

implicit def consFolder[H, T <: HList, T1, T2 >: H](implicit m :
Folder[T, T1, T2]) =
Folder[HCons[H, T], T1, T2]((l, v, fn) => m.fn(l.tail, fn(v,
l.head), fn))

def foldLeft[L <: HList, T1, T2](l : L, v : T1, fn : (T1, T2) =>
T1)(implicit f : Folder[L, T1, T2]) = f.fn(l, v, fn)

def main(args : Array[String]) {
val intList = HCons(10, HCons(1, HNil))
val anyList = HCons(10, HCons("Hello", HNil))

println(map(intList, (i : Any) => 4))
println(map(anyList, (i : Any) => 4))
println(map(intList, (i : Int) => i * 2))
// Error: println(map(anyList, (i : Int) => i * 2))

println(foldLeft(intList, true, (a : Boolean, b : Int) => b > 0))
// Error: println(foldLeft(anyList, true, (a : Boolean, b : Int) =>
b > 0))
}
}

/Jesper Nordenberg

Adriaan Moors wrote:
> I was just writing some boilerplate code that could be removed if TupleX
> supported map/forall/... uniformly
>
> I haven't thought deeply about whether it is possible, but my code looks
> like this:
>
> type ContainsBinder[T] = T => Nominal[T]
>
> trait Nominal[Self] {
> def swap(a: Name, b: Name): Self
> def fresh(a: Name): Boolean
> }
>
> implicit def PairIsNominal[T : ContainsBinder, U: ContainsBinder] =
> (self: (T, U)) => new Nominal[(T, U)] {
> def swap(a: Name, b: Name) = (self._1.swap(a, b), self._2.swap(a, b))
> def fresh(a: Name) = self._1.fresh(a) && self._2.fresh(a)
> }
>
> Could your HList approach be used to generalise PairIsNominal to deal
> with all Tuples whose element types are context bound by ContainsBinder?
>
> adriaan
>
> On Mon, Sep 14, 2009 at 2:48 PM, Jesper Nordenberg > wrote:
>
> I've posted a blog entry about type lists in Scala. These can be
> used together with an array to implement a generic, type safe tuple
> class in a simple and, I believe, novel way. Link:
>
> http://jnordenberg.blogspot.com/2009/09/type-lists-and-heterogeneously-t...
>
> /Jesper Nordenberg
>
>
> Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm
>
>