Before even getting to F-bounded Polymorphism there is construction that underpin it that i already have a hard time to understand.
trait Container[A]
trait Contained extends Container[Contained]
That construction which seem to be a trivial object oriented thing to do as it also exist in java, is already slightly puzzling me.
The issue is that when i see this trait Contained extends Container[Contained]
it feels like an infinite type recursion to me.
When we define the type List even tho we have Cons[A](a:A, tail:List[A])
, we also have case object Nil
. So the recursion can end with Nil.
But here, i don't understand how we are not in an infinite recursion ? And why it works.
Can someone care to un-confused me about it ? Or if there is any documentation, blog, or whatever can explain how this works, or maybe is implemented.
I think your question is driven by confusion about the meaning of the term
recursive type
and the difference betweenkind
,type
, andclass
.Lets first address the
recursive type
. Sometimes people mis-userecursive type
to actually mean that thistype
corresponds to a data structure which recursively contains itself.Following
Tree
is arecursive data strcuture
but not arecursive type
,Whereas, something like following is not a
recursive data strcuture
but it's arecursive type
.Interestingly, this is also related to the "importance" of some debated features of many modern languages -
null
andmutability
.So, lets say you were one of the designers of an Java language (back in early 2000's) and wanted to empower your users by adding support for generic programming.
You expect your users to be able to define generic contracts for their classes. For example, a contract for mergable classes.
Which is perfectly fine. But, this also opens the door for something like following
And this is where the problem starts. How will you ever be able to create an instance of
Human
?But they had an "awesome" solution for it. Just use
null
and keep thebrother
mutable
(don't usefinal
).But
scala.collection.immutable.List
(and theTree
created above) data strcuture in Scala is very similar to this. And we don't likenull
andmutability
.This is possible in Scala only due to support for
type parameter variance
and the specialbottom type
calledNothing
.Now, lets talk about
kind
,type
andclass
.type
can be thought as a definedcontract
.class
can be thought as the runtime implementation of the abovecontract
.kind
is actually atype
constructor. It needs atype parameter
to construct thetype
.Lets take following
List
as an example,Note :: I am intentionally not using
case object
orcase class
to avoid the confusions caused by companion objects.Here,
kind
forMyList
isF[+A]
.kind
forMyCons
isF[+A]
.kind
forMyNil
isA
.MyList
has no correspondingtype
, but it has a corresponding classMyList
.MyCons
has no correspondingtype
, but it has a corresponding classMyCons
.MyNil
has a correspondingtype
MyNil
and a corresponding classMyNil
.These corresponding
type
(available at only compile-time in most languages) andclass
(which exist at run-time) are bound tovariables
when they are created.In
val l: MyCons[Int] = new MyCons(1, new MyNil)
,l
will have typeMyCons[Int]
and runtime classMyCons
(which will be an instance ofClass[_ <: MyCons[Int]]
).But, in
val l: MyList[Int] = new MyCons(1, new MyNil)
,l
will have typeMyList[Int]
and run-time classMyCons
(which will be an instance ofClass[_ <: MyList[Int]]
).Now, lets talk about the actual
recursive types
? We said earlier that a recursive type looks like following,But saying that the above is a recursive type is kind of wrong. It is more accurate to say that
Mergeable
is akind
which can result inrecursive
types.But, if we remove make that
A
invariant then thiskind
can not result inrecursive types
.These
recursive types
are different fromF-Bound polymorphism
.The following is
F-Bound
but notrecursive
Here,
kind
ofFruit
isF[A <: iw$Fruit[A]]
. And we are adding an upper bound onA
that saysA
has to besub-type
ofFruit[A]
(which is anF
). This is where the nameF-Bound
comes from.The following is both
F-Bound
andrecursive
.Here,
kind
ofFruit
isF[+A <: iw$Fruit[A]]
.Now, I can specify the type of any
Apple
at many recursive depths.Any language which does not support
higher kinds
can not haveF-bound types
.Now, we can finally come to your doubt where you are thinking about the infinite loop.
Like we said earlier, a
type
can be thought to be like alabel
used to refer to a certain contract. So, thateager looping
actually does not happen.(I think) Scala compiler uses the
implicit evidences
(=:=
,<:<
constraints) for type comparisions. Theseevidences
are lazily generated by the compiler by using thetype bounds
ontype parameters
. So, thecompiler
has the capabilty of recursilvely generating theevidences
fortype of any depth
among theserecursive types
.So, if you have code
Only then will the compiler require to "think" about this type
Fruit[Fruit[Fruit[Fruit[Apple]]]]
and it's comparision with typeApple
.It will then be able to generate evidence
Apple <:< Fruit[Fruit[Fruit[Fruit[Apple]]]]
by using the type relationApple <: Fruit[Apple]
(provided by inheritence) andFruit[T2] <: Fruit[T1]
for anyT2 <: T1
(prvided by co-variance ofA
in kindFruit[A]
). And thus the above code will successfullytype-check
.And in case, if this
implicit evidence generation
somehow encounters a loop, it actually will not be an issue because this is already taken care of in implicit resolution/generation rules.If you look at the implicit resolution rules at https://www.scala-lang.org/files/archive/spec/2.13/07-implicits.html, you will find following
So, the moment Scala compiler finds a loop in implicit constrant search, it will choose that constraint and avoid going into infinite loop.