- About Scala
- Documentation
- Code Examples
- Software
- Scala Developers
Implementing ForwardList - Typing question
Mon, 2011-11-21, 11:05
Hi all,
I am trying to implement forward lists. I was inspired by some Haskell code found here : http://files.codersbase.com/thesistalk.pdf (page 20). Here is how I want to use/create forward lists :
class F [A, B] (a : A, b : B)object F { def apply [A, B] (a : A, b : B) = new F (a, b)}
F ("a", 1) :>: F (1, 'a') :>: Nil // is correct and should have type : ForwardList [F, String, Char] F ("a", 1) :>: F ("b", 2) :>: Nil // should not compile, type error : adding an element to a ForwardList [F, String, Int] should be of type F [_, String]
I hope it is clear enough...
Here is what I have so far :
sealed trait ForwardList [+A [_, _], +X, +Y]
case object NilFL extends ForwardList [Nothing, Nothing, Nothing]
case class Cons [X1, Y1, Z1, B [_, _]] (hd : B [X1, Y1], tl : ForwardList [B, Y1, Z1]) extends ForwardList [B, X1, Z1]
I want to add that :>: method and I can't figure how to make the types match. I had a look at the List source code I have three questions : 1. (simple) Can I "extends" the Nil object to be able to use it with both ForwardLists and Lists ?2. When creating a list like that : 1 :: 2 :: Nil. Which "::" is called? The case class :: or the :: method in the List trait ? Do I want to call my case class ":>:" instead of Cons ? 3. I put some "+" in front of my types, seeking advices from the compiler. But I have to confess, I am not sure where I want my types to be covariant and why... any idea ? Do I need some "+" in the Cons case class too ?
Thanks in advance !
Gabriel
I am trying to implement forward lists. I was inspired by some Haskell code found here : http://files.codersbase.com/thesistalk.pdf (page 20). Here is how I want to use/create forward lists :
class F [A, B] (a : A, b : B)object F { def apply [A, B] (a : A, b : B) = new F (a, b)}
F ("a", 1) :>: F (1, 'a') :>: Nil // is correct and should have type : ForwardList [F, String, Char] F ("a", 1) :>: F ("b", 2) :>: Nil // should not compile, type error : adding an element to a ForwardList [F, String, Int] should be of type F [_, String]
I hope it is clear enough...
Here is what I have so far :
sealed trait ForwardList [+A [_, _], +X, +Y]
case object NilFL extends ForwardList [Nothing, Nothing, Nothing]
case class Cons [X1, Y1, Z1, B [_, _]] (hd : B [X1, Y1], tl : ForwardList [B, Y1, Z1]) extends ForwardList [B, X1, Z1]
I want to add that :>: method and I can't figure how to make the types match. I had a look at the List source code I have three questions : 1. (simple) Can I "extends" the Nil object to be able to use it with both ForwardLists and Lists ?2. When creating a list like that : 1 :: 2 :: Nil. Which "::" is called? The case class :: or the :: method in the List trait ? Do I want to call my case class ":>:" instead of Cons ? 3. I put some "+" in front of my types, seeking advices from the compiler. But I have to confess, I am not sure where I want my types to be covariant and why... any idea ? Do I need some "+" in the Cons case class too ?
Thanks in advance !
Gabriel
Mon, 2011-11-21, 13:47
#2
Re: Implementing ForwardList - Typing question
Sorry about my mail.
I didn't read yours fully.
Mon, 2011-11-21, 14:07
#3
Re: Implementing ForwardList - Typing question
I take a second chance to answer:
abstract class FL[M[_,_],A,B]{
def :>:[C] (m : M[C,A]) : FL [M,C,B] = new :>:[M,C,B,A](m, this)
}
case class FNIl[M[_,_],A,B] extends FL[M,A,B]
case class :>: [M[_,_],A,B,C] (hd : M[A,C], tl: FL[M,C,B] ) extends FL[M,A,B]
(without the variance annotations. see 3.)
1. You can probably use implicits to convert List[Nothing] to a FList of any type.
2. I am not sure which is called. You might want to call it :>: for a nicer pattern macthing. Or you can define an extractor for :>:
http://www.scala-lang.org/node/112
3. I am not sure about you variance. You will want to use it sometimes as a pipeline of functions, and then
the first argument of M must be contravariant. But then the second argument of a cons is the first argument of the tail...
If you fix a variance for M, like for example if M behaves as a function, you can generalise your types a bit and have:
abstract class FL[M[-_,+_],-A,+B]
{
def :>:[C, D <: A] (m : M[C,D]) : FL [M,C,B] = new :>:[M,C,B,D,A](m, this)
}
case class FNIl[M[-_,+_],-A,+B] extends FL[M,Any,Nothing]
case class :>: [M[-_,+_],-A,+B,C,D >: C] (hd : M[A,C], tl: FL[M,D,B] ) extends FL[M,A,B]
Here you allow the types in your list not too match as long as they have the right subtype constraint.
Hope that helps,
Best ,
Nicolas
Mon, 2011-11-21, 15:17
#4
Re: Implementing ForwardList - Typing question
Perfect, that is exactly what I wanted! I realise that my problem came from the order of the parameters in the :>: case class and the :>: method... It's clear now, thanks!
I don't know yet if I will need the more generic version, I'll keep it in mind though.
Note about syntax : scala case class have to be defined with a parameter list. In my case, FNil has parameters so I have to add () as parameter list in the case class definition. So when using it that way : x :>: FNil compiler complains (value :>: is not a member of object FNil) so I have to add the empty parameter list x :>: FNil ()Is there a syntax trick to avoid adding the empty parameter list ?
Gabriel
2011/11/21 nicolas.oury@gmail.com <nicolas.oury@gmail.com>
I don't know yet if I will need the more generic version, I'll keep it in mind though.
Note about syntax : scala case class have to be defined with a parameter list. In my case, FNil has parameters so I have to add () as parameter list in the case class definition. So when using it that way : x :>: FNil compiler complains (value :>: is not a member of object FNil) so I have to add the empty parameter list x :>: FNil ()Is there a syntax trick to avoid adding the empty parameter list ?
Gabriel
2011/11/21 nicolas.oury@gmail.com <nicolas.oury@gmail.com>
I take a second chance to answer: abstract class FL[M[_,_],A,B]{def :>:[C] (m : M[C,A]) : FL [M,C,B] = new :>:[M,C,B,A](m, this)
}
case class FNIl[M[_,_],A,B] extends FL[M,A,B]
case class :>: [M[_,_],A,B,C] (hd : M[A,C], tl: FL[M,C,B] ) extends FL[M,A,B]
(without the variance annotations. see 3.)
1. You can probably use implicits to convert List[Nothing] to a FList of any type.
2. I am not sure which is called. You might want to call it :>: for a nicer pattern macthing. Or you can define an extractor for :>:
http://www.scala-lang.org/node/112
3. I am not sure about you variance. You will want to use it sometimes as a pipeline of functions, and then
the first argument of M must be contravariant. But then the second argument of a cons is the first argument of the tail...
If you fix a variance for M, like for example if M behaves as a function, you can generalise your types a bit and have:
abstract class FL[M[-_,+_],-A,+B]
{
def :>:[C, D <: A] (m : M[C,D]) : FL [M,C,B] = new :>:[M,C,B,D,A](m, this)
}
case class FNIl[M[-_,+_],-A,+B] extends FL[M,Any,Nothing]
case class :>: [M[-_,+_],-A,+B,C,D >: C] (hd : M[A,C], tl: FL[M,D,B] ) extends FL[M,A,B]
Here you allow the types in your list not too match as long as they have the right subtype constraint.
Hope that helps,
Best ,
Nicolas
Mon, 2011-11-21, 16:27
#5
Re: Implementing ForwardList - Typing question
On Mon, Nov 21, 2011 at 03:09:00PM +0100, Gabriel Cardoso wrote:
> Note about syntax : scala case class have to be defined with a parameter
> list. In my case, FNil has parameters so I have to add () as parameter list
> in the case class definition.
Maybe you want to be using a case object instead of a case class?
Mon, 2011-11-21, 16:57
#6
Re: Implementing ForwardList - Typing question
FNil is parametrized so I need a class...
2011/11/21 Erik Osheim <erik@plastic-idolatry.com>
2011/11/21 Erik Osheim <erik@plastic-idolatry.com>
On Mon, Nov 21, 2011 at 03:09:00PM +0100, Gabriel Cardoso wrote:
> Note about syntax : scala case class have to be defined with a parameter
> list. In my case, FNil has parameters so I have to add () as parameter list
> in the case class definition.
Maybe you want to be using a case object instead of a case class?
Mon, 2011-11-21, 17:07
#7
Re: Implementing ForwardList - Typing question
On Mon, Nov 21, 2011 at 4:49 PM, Gabriel Cardoso <gcardoso.w@gmail.com> wrote:
If you make FL covariant in all it's type parameters, you can define:
object FNil extends FL[Nothing, Nothing, Nothing]
Nothing is kind-overloaded, so can be used in a place where a type constructor is expected.
Alternatively, leave it as it, and create a data constructor function that:
def fnil[M[_,_],A,B]: FNil[M, A, B]
Or better:
def fnil[M[_,_],A,B]: FL[M, A, B]
-jason
FNil is parametrized so I need a class...
2011/11/21 Erik Osheim <erik@plastic-idolatry.com>
On Mon, Nov 21, 2011 at 03:09:00PM +0100, Gabriel Cardoso wrote:
> Note about syntax : scala case class have to be defined with a parameter
> list. In my case, FNil has parameters so I have to add () as parameter list
> in the case class definition.
Maybe you want to be using a case object instead of a case class?
If you make FL covariant in all it's type parameters, you can define:
object FNil extends FL[Nothing, Nothing, Nothing]
Nothing is kind-overloaded, so can be used in a place where a type constructor is expected.
Alternatively, leave it as it, and create a data constructor function that:
def fnil[M[_,_],A,B]: FNil[M, A, B]
Or better:
def fnil[M[_,_],A,B]: FL[M, A, B]
-jason
Mon, 2011-11-21, 18:07
#8
Re: Implementing ForwardList - Typing question
Thank you ;)
I'll go for the second proposition !
Cheers
Gabriel
2011/11/21 Jason Zaugg <jzaugg@gmail.com>
I'll go for the second proposition !
Cheers
Gabriel
2011/11/21 Jason Zaugg <jzaugg@gmail.com>
On Mon, Nov 21, 2011 at 4:49 PM, Gabriel Cardoso <gcardoso.w@gmail.com> wrote:
FNil is parametrized so I need a class...
2011/11/21 Erik Osheim <erik@plastic-idolatry.com>
On Mon, Nov 21, 2011 at 03:09:00PM +0100, Gabriel Cardoso wrote:
> Note about syntax : scala case class have to be defined with a parameter
> list. In my case, FNil has parameters so I have to add () as parameter list
> in the case class definition.
Maybe you want to be using a case object instead of a case class?
If you make FL covariant in all it's type parameters, you can define:
object FNil extends FL[Nothing, Nothing, Nothing]
Nothing is kind-overloaded, so can be used in a place where a type constructor is expected.
Alternatively, leave it as it, and create a data constructor function that:
def fnil[M[_,_],A,B]: FNil[M, A, B]
Or better:
def fnil[M[_,_],A,B]: FL[M, A, B]
-jason
What about:
abstract class FL[M[_,_],A,B]
case class FNIl[M[_,_],A,B] extends FL[M,A,B]
case class :>: [M[_,_],A,B,C] (hd : M[A,C], tl: FL[M,C,B] ) extends FL[M,A,B]