Today we become Jedi knights.
We'll explore Scala's type system, its features and rules.

You can find today's contents here.

Let us have a small version of the Cons-based list we implemented in the previous labs:

trait CBL {
    def head: Int
    def tail: CBL
    def prepend(i: Int): CBL
 
    def append(list: CBL) : CBL
 
    def map(f: Int => Int): CBL
    def flatMap(f: Int => CBL): CBL
    def filter(f: Int => Boolean): CBL
}
 
case object CNil extends CBL {
    def head: Int = throw new Exception("nothing")
    def tail: CBL = throw new Exception("nothing")
    def prepend(i: Int): CBL = Cons(i, this)
 
    def append(list: CBL): CBL = list
 
    def map(f: Int => Int): CBL = CNil
    def flatMap(f: Int => CBL): CBL = CNil
    def filter(f: Int => Boolean): CBL = CNil
}
 
case class Cons(h: Int, t: CBL) extends CBL {
    def head: Int = h
    def tail: CBL = t
    def prepend(i: Int): CBL = Cons(i, this)
 
    def append(list: CBL): CBL = Cons(h, t append list)
 
    def map(f: Int => Int): CBL = Cons(f(h), t map f)
    def flatMap(f: Int => CBL): CBL = f(h) append (t flatMap f)
    def filter(f: Int => Boolean): CBL =
        if (f(h)) Cons(h, t filter f)
        else t filter f
}

1. Genericize the above code. That is, make the list able to store any kind of elements.
   All the functions must still work.
2. If you haven't done this already at the previous exercise, make the list covariant.
   Solve the inherent compiler problems so that all the defined functions still work.
3. Let us have a method

   def f(x: { def head: A }): Unit = println(x.head)

   How does this code work?
   Do what you need to be able to pass a CBL to this method. Test it!

4. Extract the { def head: A } into a type.
   Be careful with the generic type A.
5. Create a generic class which has the method def head: A.
   Pass an instance of this class to the above method f.
   How does this work?
6. Create a class which has an equivalence =::= method for types which have the def head: A method.
   Test it with an instance of CBL and an instance of the class you defined earlier.
   Does this work if the type parameters in CBL and (yourclass) are different, i.e. CBL[Int] and YourClass[String]?