This page is no longer maintained — Please continue to the home page at www.scala-lang.org

Implementing ForwardList - Typing question

8 replies
Gabriel Cardoso
Joined: 2011-07-06,
User offline. Last seen 42 years 45 weeks ago.
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
nicolas.oury@gm...
Joined: 2011-02-13,
User offline. Last seen 42 years 45 weeks ago.
Re: Implementing ForwardList - Typing question

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] 


nicolas.oury@gm...
Joined: 2011-02-13,
User offline. Last seen 42 years 45 weeks ago.
Re: Implementing ForwardList - Typing question
Sorry about my mail.  I didn't read yours fully.
nicolas.oury@gm...
Joined: 2011-02-13,
User offline. Last seen 42 years 45 weeks ago.
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 





Gabriel Cardoso
Joined: 2011-07-06,
User offline. Last seen 42 years 45 weeks ago.
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 [dot] oury [at] gmail [dot] com <nicolas [dot] oury [at] gmail [dot] 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 






d_m
Joined: 2010-11-11,
User offline. Last seen 35 weeks 2 days ago.
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?

Gabriel Cardoso
Joined: 2011-07-06,
User offline. Last seen 42 years 45 weeks ago.
Re: Implementing ForwardList - Typing question
FNil is parametrized so I need a class...

2011/11/21 Erik Osheim <erik [at] plastic-idolatry [dot] 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?

Jason Zaugg
Joined: 2009-05-18,
User offline. Last seen 38 weeks 5 days ago.
Re: Implementing ForwardList - Typing question
On Mon, Nov 21, 2011 at 4:49 PM, Gabriel Cardoso <gcardoso [dot] w [at] gmail [dot] com> wrote:
FNil is parametrized so I need a class...

2011/11/21 Erik Osheim <erik [at] plastic-idolatry [dot] 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
Gabriel Cardoso
Joined: 2011-07-06,
User offline. Last seen 42 years 45 weeks ago.
Re: Implementing ForwardList - Typing question
Thank you ;)
I'll go for the second proposition !
Cheers
Gabriel

2011/11/21 Jason Zaugg <jzaugg [at] gmail [dot] com>
On Mon, Nov 21, 2011 at 4:49 PM, Gabriel Cardoso <gcardoso [dot] w [at] gmail [dot] com> wrote:
FNil is parametrized so I need a class...

2011/11/21 Erik Osheim <erik [at] plastic-idolatry [dot] 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

Copyright © 2012 École Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland