|
[scala] higher-kinded types
All, Am i correct in concluding that the solution in The Moors-Piessens-Odersky paper only works with collections that have been clever enough to have used type members rather that type parameters? Or, is there a trick to making the vast majority of the collections types that are parametrically typed look as if they have type members? (See example below.)
Best wishes, --greg // Paraphrasing the basic Moors-Piessens-Odersky construction trait TypeCtor1 { type E } trait Brace[A] extends TypeCtor1 { type C <: TypeCtor1 def nest( a : A ) : C{type E = A}
def flatten( bsq : C{type E=C{type E=A}} ) : C{type E=A} } // Now, how to make a version of BraceList since List is parametrically typed? -- L.G. Meredith Managing Partner Biosimilarity LLC
1219 NW 83rd St Seattle, WA 98117 +1 206.650.3740 http://biosimilarity.blogspot.com
|
|
[scala] Re: higher-kinded types
All, The following code works without going through the M-P-O construction. It enjoys approximately the same brevity as a Haskell type class. // smallest expression of monad i can find trait MBrace[C[_] <: MBrace[C,A],A] {
def nest( a : A ) : C[A] def flatten[T <: C[C[A]]]( bsq : T ) : C[A] } // one of the simplest witnesses of monad i can find class MBraceSeq[A]( a_ : A* ) extends Seq[A] with MBrace[MBraceSeq,A] {
override def nest( a : A ) = new MBraceSeq[A]( a ) override def flatten[T <: MBraceSeq[MBraceSeq[A]]]( bsq : T ) : MBraceSeq[A] = { (new MBraceSeq[A]( ) /: bsq)( { ( acc : MBraceSeq[A], e : MBraceSeq[A] ) => ( acc ++ e ).asInstanceOf[MBraceSeq[A]]
} ) } override def length = a_.length override def elements = a_.elements override def apply( n : Int ) = a_.apply( n ) } Best wishes, --greg On Wed, Jun 24, 2009 at 3:49 PM, Meredith Gregory <lgreg.meredith@...> wrote:
All,
Am i correct in concluding that the solution in The Moors-Piessens-Odersky paper only works with collections that have been clever enough to have used type members rather that type parameters? Or, is there a trick to making the vast majority of the collections types that are parametrically typed look as if they have type members? (See example below.)
Best wishes,
--greg
// Paraphrasing the basic Moors-Piessens-Odersky construction
trait TypeCtor1 { type E }
trait Brace[A] extends TypeCtor1 {
type C <: TypeCtor1
def nest( a : A ) : C{type E = A}
def flatten( bsq : C{type E=C{type E=A}} ) : C{type E=A}
}
// Now, how to make a version of BraceList since List is parametrically typed?
--
L.G. Meredith
Managing Partner
Biosimilarity LLC
1219 NW 83rd St
Seattle, WA 98117
+1 206.650.3740
http://biosimilarity.blogspot.com
-- L.G. Meredith Managing Partner Biosimilarity LLC 1219 NW 83rd St Seattle, WA 98117 +1 206.650.3740 http://biosimilarity.blogspot.com
|
|
Re: [scala] Re: higher-kinded types
Hi,
I think you meant to write
trait MBrace[C[X] <: MBrace[C,X], A]
instead of
trait MBrace[C[_] <: MBrace[C,A], A]
We only used type members in our (OOPSLA) paper to hide some of the higher-kinded types away for backward compatibility.
I would not advocate encoding type constructors using something like your TypeCtor1 trait, as the encoding makes type&kind checking less precise, and you'll lose type inference (type constructor inference should be coming to 2.8.x, btw).
cheers adriaan
On Thu, Jun 25, 2009 at 8:47 AM, Meredith Gregory <lgreg.meredith@...> wrote:
All,
The following code works without going through the M-P-O construction. It enjoys approximately the same brevity as a Haskell type class.
// smallest expression of monad i can find
trait MBrace[C[_] <: MBrace[C,A],A] {
def nest( a : A ) : C[A]
def flatten[T <: C[C[A]]]( bsq : T ) : C[A]
}
// one of the simplest witnesses of monad i can find
class MBraceSeq[A]( a_ : A* ) extends Seq[A] with MBrace[MBraceSeq,A] {
override def nest( a : A ) = new MBraceSeq[A]( a )
override def flatten[T <: MBraceSeq[MBraceSeq[A]]]( bsq : T ) : MBraceSeq[A] = {
(new MBraceSeq[A]( ) /: bsq)( {
( acc : MBraceSeq[A], e : MBraceSeq[A] ) => ( acc ++ e ).asInstanceOf[MBraceSeq[A]]
} )
}
override def length = a_.length
override def elements = a_.elements
override def apply( n : Int ) = a_.apply( n )
}
Best wishes,
--greg
On Wed, Jun 24, 2009 at 3:49 PM, Meredith Gregory <lgreg.meredith@...> wrote:
All,
Am i correct in concluding that the solution in The Moors-Piessens-Odersky paper only works with collections that have been clever enough to have used type members rather that type parameters? Or, is there a trick to making the vast majority of the collections types that are parametrically typed look as if they have type members? (See example below.)
Best wishes,
--greg
// Paraphrasing the basic Moors-Piessens-Odersky construction
trait TypeCtor1 { type E }
trait Brace[A] extends TypeCtor1 {
type C <: TypeCtor1
def nest( a : A ) : C{type E = A}
def flatten( bsq : C{type E=C{type E=A}} ) : C{type E=A}
}
// Now, how to make a version of BraceList since List is parametrically typed?
--
L.G. Meredith
Managing Partner
Biosimilarity LLC
1219 NW 83rd St
Seattle, WA 98117
+1 206.650.3740
http://biosimilarity.blogspot.com
-- L.G. Meredith Managing Partner Biosimilarity LLC 1219 NW 83rd St Seattle, WA 98117 +1 206.650.3740 http://biosimilarity.blogspot.com
Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm for more information.
|
|
Re: [scala] Re: higher-kinded types
Adriaan, First of all, thanks for the time and thought you put into this. i'm not happy with your interpretation. i cannot convince myself that refinements might not relax the "A"-ness (apologies for the awful sfunctor of a pun hiding here ;-) of the contained element. More importantly, the bug is a bug regardless of whether my encoding has the semantics i want. The compiler is complaining that type bounds are not met that to my eyes plainly are -- unless you can convince me otherwise. For example, if you can give me the interpretation into the appropriate type calculus of the situation i reported, i will do the calculation myself.
Best wishes, --greg On Fri, Jun 26, 2009 at 2:35 AM, Adriaan Moors <adriaan.moors@...> wrote:
Hi,
I think you meant to write
trait MBrace[C[X] <: MBrace[C,X], A]
instead of
trait MBrace[C[_] <: MBrace[C,A], A]
We only used type members in our (OOPSLA) paper to hide some of the higher-kinded types away for backward compatibility.
I would not advocate encoding type constructors using something like your TypeCtor1 trait, as the encoding makes type&kind checking less precise, and you'll lose type inference (type constructor inference should be coming to 2.8.x, btw).
cheers adriaan
All,
The following code works without going through the M-P-O construction. It enjoys approximately the same brevity as a Haskell type class.
// smallest expression of monad i can find
trait MBrace[C[_] <: MBrace[C,A],A] {
def nest( a : A ) : C[A]
def flatten[T <: C[C[A]]]( bsq : T ) : C[A]
}
// one of the simplest witnesses of monad i can find
class MBraceSeq[A]( a_ : A* ) extends Seq[A] with MBrace[MBraceSeq,A] {
override def nest( a : A ) = new MBraceSeq[A]( a )
override def flatten[T <: MBraceSeq[MBraceSeq[A]]]( bsq : T ) : MBraceSeq[A] = {
(new MBraceSeq[A]( ) /: bsq)( {
( acc : MBraceSeq[A], e : MBraceSeq[A] ) => ( acc ++ e ).asInstanceOf[MBraceSeq[A]]
} )
}
override def length = a_.length
override def elements = a_.elements
override def apply( n : Int ) = a_.apply( n )
}
Best wishes,
--greg
On Wed, Jun 24, 2009 at 3:49 PM, Meredith Gregory <lgreg.meredith@...> wrote:
All,
Am i correct in concluding that the solution in The Moors-Piessens-Odersky paper only works with collections that have been clever enough to have used type members rather that type parameters? Or, is there a trick to making the vast majority of the collections types that are parametrically typed look as if they have type members? (See example below.)
Best wishes,
--greg
// Paraphrasing the basic Moors-Piessens-Odersky construction
trait TypeCtor1 { type E }
trait Brace[A] extends TypeCtor1 {
type C <: TypeCtor1
def nest( a : A ) : C{type E = A}
def flatten( bsq : C{type E=C{type E=A}} ) : C{type E=A}
}
// Now, how to make a version of BraceList since List is parametrically typed?
--
L.G. Meredith
Managing Partner
Biosimilarity LLC
1219 NW 83rd St
Seattle, WA 98117
+1 206.650.3740
http://biosimilarity.blogspot.com
-- L.G. Meredith Managing Partner Biosimilarity LLC 1219 NW 83rd St Seattle, WA 98117 +1 206.650.3740 http://biosimilarity.blogspot.com
Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm for more information.
-- L.G. Meredith Managing Partner Biosimilarity LLC 1219 NW 83rd St Seattle, WA 98117 +1 206.650.3740 http://biosimilarity.blogspot.com
|
|
Re: [scala] Re: higher-kinded types
Adriaan, i believe the examples below indicate that Scala's type-checker agrees with me that your proposed correction for my encoding allows for potential loosening of "A"-ness. See the example below.
In English, in a monad C over A we don't want to encounter some other type besides A's. We see the problem when we insist that A's have some property, like being at least Option'ed. Best wishes,
--greg // smallest expression of monad i can find trait MBrace[C[X] <: MBrace[C,X],A] { def nest( a : A ) : C[A] def flatten[T <: C[C[A]]]( bsq : T ) : C[A] } // a monad that is a Seq
trait MBraceSeq[C[X] <: MBrace[C,X] with Seq[X],A] extends MBrace[C,A] // This is fine abstract class MLink[A]( a : Option[A], na : Option[MLink[A]] ) extends Seq[A] with MBrace[MLink,A] // But this is not
//abstract class MLink[A <: Option[_]]( a : Option[A], na : Option[MLink[A]] ) extends Seq[A] with MBrace[MLink,A] The complaint is exactly in line with my concern: scala> <console>:6: error: the kinds of the type arguments (MLink,A) do not conform to the expected kinds of the type parameters (type C,type A) in trait MBrace.
MLink's type parameters do not match type C's expected parameters: type A's bounds >: Nothing <: Option[_] are stricter than type X's declared bounds >: Nothing <: Any abstract class MLink[A <: Option[_]]( a : Option[A], na : Option[MLink[A]] ) extends Seq[A] with MBrace[MLink,A]
On Fri, Jun 26, 2009 at 10:24 AM, Meredith Gregory <lgreg.meredith@...> wrote:
Adriaan,
First of all, thanks for the time and thought you put into this. i'm not happy with your interpretation. i cannot convince myself that refinements might not relax the "A"-ness (apologies for the awful sfunctor of a pun hiding here ;-) of the contained element. More importantly, the bug is a bug regardless of whether my encoding has the semantics i want. The compiler is complaining that type bounds are not met that to my eyes plainly are -- unless you can convince me otherwise. For example, if you can give me the interpretation into the appropriate type calculus of the situation i reported, i will do the calculation myself.
Best wishes,
--gregOn Fri, Jun 26, 2009 at 2:35 AM, Adriaan Moors <adriaan.moors@...> wrote:
Hi,
I think you meant to write
trait MBrace[C[X] <: MBrace[C,X], A]
instead of
trait MBrace[C[_] <: MBrace[C,A], A]
We only used type members in our (OOPSLA) paper to hide some of the higher-kinded types away for backward compatibility.
I would not advocate encoding type constructors using something like your TypeCtor1 trait, as the encoding makes type&kind checking less precise, and you'll lose type inference (type constructor inference should be coming to 2.8.x, btw).
cheers adriaan
All,
The following code works without going through the M-P-O construction. It enjoys approximately the same brevity as a Haskell type class.
// smallest expression of monad i can find
trait MBrace[C[_] <: MBrace[C,A],A] {
def nest( a : A ) : C[A]
def flatten[T <: C[C[A]]]( bsq : T ) : C[A]
}
// one of the simplest witnesses of monad i can find
class MBraceSeq[A]( a_ : A* ) extends Seq[A] with MBrace[MBraceSeq,A] {
override def nest( a : A ) = new MBraceSeq[A]( a )
override def flatten[T <: MBraceSeq[MBraceSeq[A]]]( bsq : T ) : MBraceSeq[A] = {
(new MBraceSeq[A]( ) /: bsq)( {
( acc : MBraceSeq[A], e : MBraceSeq[A] ) => ( acc ++ e ).asInstanceOf[MBraceSeq[A]]
} )
}
override def length = a_.length
override def elements = a_.elements
override def apply( n : Int ) = a_.apply( n )
}
Best wishes,
--greg
On Wed, Jun 24, 2009 at 3:49 PM, Meredith Gregory <lgreg.meredith@...> wrote:
All,
Am i correct in concluding that the solution in The Moors-Piessens-Odersky paper only works with collections that have been clever enough to have used type members rather that type parameters? Or, is there a trick to making the vast majority of the collections types that are parametrically typed look as if they have type members? (See example below.)
Best wishes,
--greg
// Paraphrasing the basic Moors-Piessens-Odersky construction
trait TypeCtor1 { type E }
trait Brace[A] extends TypeCtor1 {
type C <: TypeCtor1
def nest( a : A ) : C{type E = A}
def flatten( bsq : C{type E=C{type E=A}} ) : C{type E=A}
}
// Now, how to make a version of BraceList since List is parametrically typed?
--
L.G. Meredith
Managing Partner
Biosimilarity LLC
1219 NW 83rd St
Seattle, WA 98117
+1 206.650.3740
http://biosimilarity.blogspot.com
-- L.G. Meredith Managing Partner Biosimilarity LLC 1219 NW 83rd St Seattle, WA 98117 +1 206.650.3740 http://biosimilarity.blogspot.com
Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm for more information.
-- L.G. Meredith Managing Partner Biosimilarity LLC 1219 NW 83rd St Seattle, WA 98117 +1 206.650.3740 http://biosimilarity.blogspot.com
-- L.G. Meredith Managing Partner Biosimilarity LLC 1219 NW 83rd St Seattle, WA 98117 +1 206.650.3740 http://biosimilarity.blogspot.com
|
|
Re: [scala] Re: higher-kinded types
On Wed, Jul 1, 2009 at 12:25 AM, Meredith Gregory <lgreg.meredith@...> wrote:
In English, in a monad C over A we don't want to encounter some other type besides A's. Sorry, this does not make sense to me.
class Monad m where
(>>=) :: m a -> (a -> m b) -> m b
return :: a -> m a
|
instance Monad [] where
m >>= f = concatMap f m
return x = [x]
fail s = [] |
Surely a list of any type of elements is a Monad!
We see the problem when we insist that A's have some property, like being at least Option'ed. Your example does not type check because it imposes a bound on the higher-order type parameter of the Monad's type constructor that is stricter than what was originally declared. Our paper on type constructor polymorphism explains how to do this is Scala. By the way, this is impossible in Haskell. You'd need something like abstraction over type class contexts. In pseudo-code:
class Monad C m where -- C is an abstract type class context
(>>=) :: C a => m a -> (a -> m b) -> m b
return :: C a => a -> m a
instance Monad Ord Set where ... -- because Ord a => Set a
Our paper explains how this can already be done in Scala by using an abstract type as a subtype bound.
hth adriaan
|
|
Re: [scala] Re: higher-kinded types
Dear Adriaan, Thanks for your note. You are correct. i'm attempting to encode a notion richer than monad in which the type ctor is also a monad in which the type ctor is also a monad in which ... ;-) Sorry i didn't make that clear earlier. (i'm headed to encode the types described in this posting.) That's why the type is called MBrace. i'll reread the paper you reference to see if i can see how to encode this.
Best wishes, --greg On Mon, Jul 13, 2009 at 2:05 AM, Adriaan Moors <adriaan.moors@...> wrote:
On Wed, Jul 1, 2009 at 12:25 AM, Meredith Gregory <lgreg.meredith@...> wrote:
In English, in a monad C over A we don't want to encounter some other type besides A's. Sorry, this does not make sense to me.
class Monad m where
(>>=) :: m a -> (a -> m b) -> m b
return :: a -> m a
|
instance Monad [] where
m >>= f = concatMap f m
return x = [x]
fail s = [] |
Surely a list of any type of elements is a Monad!
We see the problem when we insist that A's have some property, like being at least Option'ed. Your example does not type check because it imposes a bound on the higher-order type parameter of the Monad's type constructor that is stricter than what was originally declared. Our paper on type constructor polymorphism explains how to do this is Scala. By the way, this is impossible in Haskell. You'd need something like abstraction over type class contexts. In pseudo-code:
class Monad C m where -- C is an abstract type class context
(>>=) :: C a => m a -> (a -> m b) -> m b
return :: C a => a -> m a
instance Monad Ord Set where ... -- because Ord a => Set a
Our paper explains how this can already be done in Scala by using an abstract type as a subtype bound.
hth adriaan
-- L.G. Meredith Managing Partner Biosimilarity LLC 1219 NW 83rd St Seattle, WA 98117 +1 206.650.3740 http://biosimilarity.blogspot.com
|
