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

Making the type for non-empty lists be useful

3 replies
ewilligers
Joined: 2008-08-20,
User offline. Last seen 3 years 17 weeks ago.

[BTW is Trac down? "Firefox has detected that the server is redirecting
the request for this address in a way that will never complete. The
browser has stopped trying to retrieve the requested item. The site is
redirecting the request in a way that will never complete."]

Here's a two-part suggestion for a minor change to List:

(a) The return type of List's def :: should be :: instead of List
(b) class :: should be covariant

I think part (a) has been suggested on the mailing list.

Part (b) had been submitted 4 years ago

https://lampsvn.epfl.ch/trac/scala/changeset/3869
made the type argument of :: covariant

but it isn't in the current code (e.g. 2.8.0.r16887-b20090112021721)

In my attached example we have a function

def mean(xs: scala.::[Number]) = xs.reduceLeft(_ + _) / xs.length

that accepts non-empty lists of numbers. Unfortunately, none of the
following are accepted as non-empty lists of numbers.

Real(1) :: Nil
(Real(1): Number) :: Nil
(Real(1) :: Nil).asInstanceOf[scala.::[Real]]

When we use a list that has (a) and (b), there's no problem.
(Demonstrated in the second half of the attached file, with my >>
reverse list from earlier today.)

Carsten Saager
Joined: 2008-12-19,
User offline. Last seen 42 years 45 weeks ago.
Re: Making the type for non-empty lists be useful


On Tue, Jan 13, 2009 at 4:39 AM, Eric Willigers <ewilligers [at] gmail [dot] com> wrote:
[BTW is Trac down? "Firefox has detected that the server is redirecting the request for this address in a way that will never complete. The browser has stopped trying to retrieve the requested item. The site is redirecting the request in a way that will never complete."]

I have the same problem




Here's a two-part suggestion for a minor change to List:

(a) The return type of List's def :: should be :: instead of List
(b) class :: should be covariant


+1
 



I think part (a) has been suggested on the mailing list.

Part (b) had been submitted 4 years ago

   https://lampsvn.epfl.ch/trac/scala/changeset/3869
   made the type argument of :: covariant

but it isn't in the current code (e.g. 2.8.0.r16887-b20090112021721)



In my attached example we have a function

 def mean(xs: scala.::[Number]) = xs.reduceLeft(_ + _) / xs.length

that accepts non-empty lists of numbers. Unfortunately, none of the following are accepted as non-empty lists of numbers.

Real(1) :: Nil
(Real(1): Number) :: Nil
(Real(1) :: Nil).asInstanceOf[scala.::[Real]]


When we use a list that has  (a) and (b),  there's no problem. (Demonstrated in the second half of the attached file, with my >> reverse list from earlier today.)


package pkg

abstract class Number {
   def value: double
   def +(that: Number): Number = Real(value + that.value)
   def /(that: Int): Number = Real(value / that)
}

case class Real(value: double) extends Number {}


// shows compilation failures with the current definition of List

object Test extends Application {

def mean(xs: scala.::[Number]) = xs.reduceLeft(_ + _) / xs.length

{
val numbers = Real(1) :: Nil

println(mean(numbers))
// gives error: type mismatch;
// found   : List[Real]
// required: ::[Number]
}

{
val numbers = (Real(1): Number) :: Nil

println(mean(numbers))
// gives error: type mismatch;
// found   : List[Number]
// required: ::[Number]
}

{
val numbers = (Real(1) :: Nil).asInstanceOf[scala.::[Real]]

println(mean(numbers))
// gives error: type mismatch;
// found   : ::[Real]
// required: ::[Number]
}

}



// Example of how compilation succeeds when using a simple list class that has the proposed changes

sealed abstract class ReverseList[+A] {
   // List method :: currently returns a List, it could return a ::
   def >>[B >: A](x: B): >>[B] = pkg.>>(this, x)
}

final case object ReverseNil extends ReverseList[Nothing] {
}

// :: isn't covariant, it could be
final case class >>[+A](tail: ReverseList[A], head: A) extends ReverseList[A] {
}

object Test2 extends Application {

def mean(xs: pkg.>>[Number]) = Real(0) // implementation not relevant

{
val numbers = ReverseNil >> Real(1)

println(mean(numbers))
}

{
val numbers = ReverseNil >> (Real(1): Number)

println(mean(numbers))
}

{
val numbers = (ReverseNil >> Real(1)).asInstanceOf[pkg.>>[Real]]

println(mean(numbers))
}

}



ewilligers
Joined: 2008-08-20,
User offline. Last seen 3 years 17 weeks ago.
Re: Making the type for non-empty lists be useful

Eric Willigers wrote:
> Here's a two-part suggestion for a minor change to List:
>
> (a) The return type of List's def :: should be :: instead of List
> (b) class :: should be covariant

Sebastien Bocq wrote (in other thread):
> Isn't :: not covariant because it's sole intended use is pattern matching?

I suspect it is isn't covariant because hd and tl are each var (not val).

This is a complication.

One failed attempt:

final case class ::[+B](private var hd: Any, private var tl: List[Any])
extends List[B] {
def head : B = hd.asInstanceOf[B]
def tail : List[B] = tl.asInstanceOf[List[B]]
// ...
}

doesn't work because pattern matching "case x :: xs" now gives x and xs
weaker types:

error: type mismatch;
found : List[Any]
required: List[A]

found : Any
required: A

Another failed attempt:

final class ::[+B](private var hd: Any, private[pkg] var tl: List[Any])
extends List[B] {
...

object :: {
def apply[B](hd: B, tl: List[B]): pkg.::[B] = new pkg.::[B](hd, tl)

def unapply[B](cons: pkg.::[B]): Option[(B, List[B])] =
Some(cons.head, cons.tail)
}

didn't work as reduceLeft failed to compile:

warning: match is not exhaustive!
missing combination * Nil * *
*

case x0 :: x1 :: xs =>
^

I'm not sure what's wrong here.

BTW, pattern matching is part of the reason I'd like def :: to return a ::

val xs = if (x) x :: x :: Nil else x :: Nil
xs match {
case first :: Nil => 1
case first :: second :: rest => 2
}

gives warning: match is not exhaustive!
missing combination Nil

The programmer knows xs can't be Nil, the compiler should too.

odersky
Joined: 2008-07-29,
User offline. Last seen 45 weeks 6 days ago.
Re: Re: Making the type for non-empty lists be useful

I'm very nervous to change the type of ::. It might break all sorts of
things in type inference of user code.

Cheers

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