Making the type for non-empty lists be useful

[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.)


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))
}

}

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.

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

Cheers