CODEWITHSUNDEEP
listscalacons
vicwhit Mac
vicwhit Mac

Reputation: 69

Is ::[Int] the same as List[Int]?

scala> val w = new ::[Int](4,Nil)
w: scala.collection.immutable.::[Int] = List(4)

scala> val x = List[Int](4)
x: List[Int] = List(4)

What is the difference between these two expressions? Is ::[Int](4) an instance of List[int], since both ::[Int](4) and List[Int](4) yield List(4)?

Upvotes: 2

Views: 137

Answers (2)

Mario Galic
Mario Galic

Reputation: 48410

::[T] is one of the constructors of the algebraic data type List[T]. The other one is Nil. Consider the following inductive definition of a List

sealed trait List[+T]
case object Nil extends List[Nothing] 
case class ::[T](head: T, tail: List[T]) extends List[T]

:: might look a bit odd as it is purely symbolic name, and in other languages it is sometimes referred as Cons. Constructors are the means of making values of type List[T], here are a few

Nil
::(1, Nil)
::(2, ::(1, Nil))
::(42, ::(2, ::(1, Nil)))

These value, being of inductive nature, have a remarkable property of whenever we have one, we always know how to construct the following one(s). In other words, inductive values imply inductive values. For example, both

::(2, ::(1, Nil))

and 

::(51, ::(1, Nil))

are implications of ::(1, Nil) by the power of constructor ::[Int].

Is ::[Int] the same as List[Int]?

Because Scala implements algebraic data types using a form of inheritance, there indeed exists a is-a-subtype-of relationship

implicitly[::[Int] <:< List[Int]] // ok!

whilst there does not exist equal-to relationship

implicitly[::[Int] =:= List[Int]] // error!

However, in my opinion, these subtyping relationships are not the point of algebraic data type, being kind of incidental in Scala. Instead the relationship between a constructor ::[T] and a type List[T] whose values it is constructing, is more analogous to relationship between a function and a type.

Is new ::[Int](4, Nil) the same as List[Int](4)?

They both evaluate to the same value, for example the following passes

assert(new ::[Int](4, Nil) == List[Int](4))

however the way we arrive at this value is quite different. In the former case we are using directly the constructor of the List[Int] ADT, whilst in the latter case we are in fact calling apply method on the companion object of trait List[T]

List.apply[Int](4)

where apply is defined as

def apply[A](xs: A*): List[A] = xs.toList

Now in practice we rarely have to think about these things. Usually we simply write something like

List(4, 2, 42)

and be done with it. The "low level" constructor :: shows its face sometimes during pattern matching which is a way of destructuring ADTs, for example, here is recursive implementation that gets the sum of elements in a list

def sum(l: List[Int]): Int = {
  l match {
    case Nil => 0
    case head :: tail => head + sum(tail)
  }
}

sum(List(1, 2, 42)) 
// res1: Int = 45

Upvotes: 3

rau
rau

Reputation: 107

The abstract class List is sealed, so it is only extended by the class ::[+A], and the object Nil.

This means, that in order to conform to the type List[+A], an object has to be of type ::[X], where X conforms to A, or Nil, which conforms to List[Nothing].

A value of type List[Int] may well be Nil, since List[Nothing] conforms to List[Int]. On the Other hand, you cannot assign Nil to a value of type ::[Int], since it is not a ::[_].

TL;DR: Every ::[_] is a List[_], but not every List[_] is a ::[_].

Upvotes: 1

Related Questions