Coding with Variance

Banashri
Windoof-User
Windoof-User
Beiträge: 25
Registriert: 19. Dez 2013 02:55

Coding with Variance

Beitrag von Banashri »

Hi All,

I need some help in understanding variance.
Consider following question:

Sketch two designs for a generic SortableCollection trait in Scala that supports sorting. Assume that you have a base
class Collection[A] which is covariant in A. The outcome of the sorting method should be a fresh collection and the
order of elements depends on how elements are compared. One of your designs should use the template pattern and the
other the strategy pattern to parameterize the sorting process with a comparison operation. Note: You do not have to
implement the sorting method, but indicate in a comment where you use the comparison operation.

I am trying to write to implement this.
Is the method signature with types correct? I am confused about using types.
Would the method signature be: def sort[A](collection: Collection[A]) : Collection[A], or something written below?

Code: Alles auswählen


class Collection[+A] {

def sort[U >:A](collection: Collection[U]): Collection[U] = { ... }

}

Assax
Windoof-User
Windoof-User
Beiträge: 41
Registriert: 2. Dez 2011 10:38

Re: Coding with Variance

Beitrag von Assax »

I asked this same question on friday to one of the assistants.

He said that it should be Collection[+A] for the collection itself and in the interface for example the method signature should be

Code: Alles auswählen

sort[B<:A](c: Collection[B]): Collection[B] 

Note that you wouldnt define the sort method inside your collection though but rather in the interface or abstract class (whichever pattern you apply) and inside the Collection[+A] I think you'd just go

Code: Alles auswählen

def sort = { stragegy.sort(this)}
for example.

Btw can you explain to me the intent of applying sort on a supertype ( U )? Wouldn't this be contravariant??
Edit: Ok reading up on this contravariance there is the only thing that would be accepted by the compiler in that case because parameteres are supposed to be contravariant for functions.

But I also always get confused with generics in scala in terms of co and contravariance...
Wouldn't the whole point of defining collection as Collection[+A] be that Collection is seen as a subtype for Collection[A]?
If so then why is the sort signature not

Code: Alles auswählen

sort[A](c: Collection[A]): Collection[A] = {....}
Now since we declared Collection over the type +A we could still pass a Collection into sort?

Banashri
Windoof-User
Windoof-User
Beiträge: 25
Registriert: 19. Dez 2013 02:55

Re: Coding with Variance

Beitrag von Banashri »

I found some rules on allowed Variance positions, finally. :D

Covariant type parameters can be used as return types only:

Code: Alles auswählen

 abstract class SomeClass[+A] { def someMethod(): A } 
is allowed.

Workaround to use a covariant type in a method parameter type:

Code: Alles auswählen

abstract class SomeClass[+A] { def someMethod[B >: A](b: B) }
Contravariant type parameters can be used as types of method parameters only:

Code: Alles auswählen

 abstract class SomeClass[-A] { def someMethod(a: A)  }
is allowed.

Workaround to use a contravariant type in a return type:

Code: Alles auswählen

abstract class SomeClass[-A] { def someMethod[B <: A](): B }

m.hosseinian
Windoof-User
Windoof-User
Beiträge: 34
Registriert: 3. Mai 2015 21:28

Re: Coding with Variance

Beitrag von m.hosseinian »

So, could you upload your final answer to this question?
mine is this:

Code: Alles auswählen

Template method:
trait SortableCollection[+A] extends Collection[A] {
	def sort(): SortableCollection[A] = {
		//...
		// compair method is called here <=
		//...
	}
	def compair(index: Int): Boolean
}
Strategy:
trait SortableCollection[+A] extends Collection[A] {
	def sort(compare: (A, A) => Boolean): SortableCollection[A] = {
		//...
		// compair is used here <=
		//...
	}
}
Template:
 + high level policy/algorithm is decoupled from low level implementations
 - low level mechanisms are not reusable
Strategy:
 + low level mechanism could be shared among different algorithms
 - the interface between the strategy and the clients could bloat due to support of various clients

Banashri
Windoof-User
Windoof-User
Beiträge: 25
Registriert: 19. Dez 2013 02:55

Re: Coding with Variance

Beitrag von Banashri »

Almost same as yours!

Code: Alles auswählen


abstract class Collection[+A]

trait SortableCollection[+A] extends Collection[A] {
	def compare[U](elem1: U, elem2: U): Boolean
	def sort[U >: A](c: Collection[U]): Collection[U] = {
		//use compare
	}
}

trait SortableCollection[+A] extends Collection[A] {
   def sort[U >:A](compare: (U, U) => Boolean): SortableCollection[U] = {
      //...
      // compair is used here <=
      //...
   }
}

m.hosseinian
Windoof-User
Windoof-User
Beiträge: 34
Registriert: 3. Mai 2015 21:28

Re: Coding with Variance

Beitrag von m.hosseinian »

What I cant see is that, why you pass a collection to the sort that then you have to care for type boundaries and stuff? Isn't it that, the usage would be something like :

Code: Alles auswählen

val c: SortableCollection[Int] = ...
...
val sortedC: SortableCollection[Int] = c.sort()

Assax
Windoof-User
Windoof-User
Beiträge: 41
Registriert: 2. Dez 2011 10:38

Re: Coding with Variance

Beitrag von Assax »

Can you please explain why you both extend the Collection in your Template / Strategy patterns? I've never seen this in any of their structures.

I would have thought it was something like this:

Code: Alles auswählen

trait Sortable {

def sort[B <: A](c: Collection[B]): Collection[B] = {

...
compare((B,B))
...

}
def compare[B<:A](elements: (B,B)): B
} 

object BiggerThanSorter extends Sortable {

def compare[B<:A](elements: (B,B)): B = { ... }

}
All this generic code in scala makes my head spin.
m.hosseinian hat geschrieben:What I cant see is that, why you pass a collection to the sort that then you have to care for type boundaries and stuff? Isn't it that, the usage would be something like :

Code: Alles auswählen

val c: SortableCollection[Int] = ...
...
val sortedC: SortableCollection[Int] = c.sort()
I think that is because if you look at the template or strategy pattern you would extend from your traits to implement concrete sorters.
In your collection class you would keep a reference to the sorter and sort on your collection by calling sorter.sort(this)

m.hosseinian
Windoof-User
Windoof-User
Beiträge: 34
Registriert: 3. Mai 2015 21:28

Re: Coding with Variance

Beitrag von m.hosseinian »

Simply because it is explicitly mentioned:
Assume that you have a _base_ class Collection[A] which is covariant in A ...
This _base_ gives me enough clue that I have to extend from this Collection. Another suggestion is the name of asked trait "SortableCollection".
Assax hat geschrieben:I think that is because if you look at the template or strategy pattern you would extend from your traits to implement concrete sorters.
In your collection class you would keep a reference to the sorter and sort on your collection by calling sorter.sort(this)
I cannot get your point here! You need to design a Collection with sorting capability, (it is able to sort its own elements and return a new object. Just like List.sort in Scala does!) with outsourced comparing function (not a sorting mechanism that accepts a collection or an outsourced sorting mechanism implanted into a collection or what-so-ever). This is what I could understand from the question still, I would be so pleased if any of tutors could come and make any clearance here!

@Assax: By the way, your code would not compile, it will complain about undefined type parameter A.

Assax
Windoof-User
Windoof-User
Beiträge: 41
Registriert: 2. Dez 2011 10:38

Re: Coding with Variance

Beitrag von Assax »

m.hosseinian hat geschrieben:Simply because it is explicitly mentioned:
Assume that you have a _base_ class Collection[A] which is covariant in A ...
This _base_ gives me enough clue that I have to extend from this Collection. Another suggestion is the name of asked trait "SortableCollection".
I think what is meant was that you have a baseclass Collection[+A] and you can extend it by creating a concrete Collection class like a List or an Array. The trait sortableCollection (because we have the template and strategy pattern) are what should be the interfaces that the collection depends on to implement the sorting algorithm. As was shown in the slides similar to here: http://i.imgur.com/wWp3mm7.png where the Collection would be your Client.
m.hosseinian hat geschrieben:I cannot get your point here! You need to design a Collection with sorting capability, (it is able to sort its own elements and return a new object. Just like List.sort in Scala does!) with outsourced comparing function
The task (what I understood) was to make a Collection that is sortable with a SortableCollection trait based on the template or strategy pattern. If you keep a reference of this trait in your collection you can have it sorted by forwarding its sort call to the trait it currently references to. This way you can easily swap the referenced traits and sort by different criteria, (e.g bigger elements first, smaller elements first).

Say for example you have a concrete collection and your collection has a reference like this:

Code: Alles auswählen

var sorter: SortableCollection = new BiggerThanSortable()
(Generics aside)

your sort method inside Collection would look like this:

Code: Alles auswählen

def sort(): Collection {
sorter.sort(this)
}
(Again, Generics aside)

you could also have a setSorter method where you change the sorter that the collection uses but you wouldn't have to change the sort method.

@Assax: By the way, your code would not compile, it will complain about undefined type parameter A.[/quote]

That's likely because I'm no good with generics in Scala at all. And honestly the fact that the scala introduction only had 1 slide of generics with the easiest example possible does not help while we had 10 slides of comparison between val var and def (hint: Feedback for the future).
I am having a hard time finding any good source on how to use Generics in Scala especially when it comes to extension of classes that also have a generic type declaration like

Code: Alles auswählen

class Singleton[+A](x: A) extends Tuple[A]
I agree though that it would be great if anyone official could clarify how to do this because this question has already been asked like 3-4 times and nobody is sure how to do it correctly.

m.hosseinian
Windoof-User
Windoof-User
Beiträge: 34
Registriert: 3. Mai 2015 21:28

Re: Coding with Variance

Beitrag von m.hosseinian »

Irrelevant, but here is my running code, maybe it clears better my itention. (however, I don't like it since, it is mutable. Due to the requirement of the question that we should sketch a _trait_!)

Code: Alles auswählen

trait SortableCollection[A] extends Seq[A] {
    var elems: Seq[A]

    def sort(compare: (A, A) => Boolean): SortableCollection[A] = {
        for (i <- elems.length - 2 to 0 by -1)
            for (j <- 0 to i)
                if (!compare(elems(j), elems(j + 1)))
                     swap(j)
        this
    }

    def swap(index: Int) =
        elems = ((elems.take(index) :+ elems(index + 1) :+ elems(index)).toList ::: elems.drop(index + 2).toList)

    override def apply(idx: Int): A = elems(idx)
    override def length: Int = elems.length
    override def iterator: Iterator[A] = elems.iterator
    override def toString() = elems.mkString("{", ", ", "}")
}

class BubbleSorter[A](var elems: Seq[A]) extends SortableCollection[A] 

object BubbleSorter {
    def apply[A](elems: A*): SortableCollection[A] =
        new BubbleSorter[A](elems)
}

object main extends App {
    val coll = BubbleSorter(2, 1, 3, 5, 4)
    println(coll) //>   {2, 1, 3, 5, 4}

    val ascSortedColl = coll.sort(_ < _)
    println(ascSortedColl) //>    {1, 2, 3, 4, 5}
    
    val descSortedColl = coll.sort(_ > _)
    println(descSortedColl) //>    {5, 4, 3, 2, 1}
}

Assax
Windoof-User
Windoof-User
Beiträge: 41
Registriert: 2. Dez 2011 10:38

Re: Coding with Variance

Beitrag von Assax »

Code: Alles auswählen

object main extends App {
  
  def run() = {
    var c = new Collection(new swapSorter(), 1,2,3,4)
    println (c.printCollection())
    var u = c.sort
    println (u.printCollection())
  }
  
  class Collection[+A](sorting: SortableCollection, contains: A*) {
  
  var sorter: SortableCollection = new swapSorter()
  
    def add[B >: A](item: B): Collection[B] = {
      new Collection(sorter, (contains :+ item): _*)
    }
  
  def sort(): Collection[A] = {sorter.sort(this)}
  
  def getContains(): Seq[A] = {
    contains
  }
  
  def setSorter(s: SortableCollection) = { sorter = s }
  
  def printCollection() = { contains.toString() }
}
  
  trait SortableCollection {
  
  def sort[A](c: Collection[A]): Collection[A] = {
    val result: Collection[A] = new Collection[A](this,order(c): _*)
    result.setSorter(this)
    result   
  }
  
  def order[A](c: Collection[A]): Seq[A]
  
}
  
  class swapSorter extends SortableCollection {
  def order[A](c: Collection[A]): Seq[A] = {
    val seqnew: Seq[A] = c.getContains()
    seqnew.reverse
  }
}
  
}
This would by my implementation.
Nevermind the run etc it was just for debugging, its also not beautiful or optimized but just a rough sketch on how I would implement the task with the template method pattern.
You could now easily swap the concrete sortableCollections to get different sorting behavior.

http://pastebin.com/bD0gsKSe

dat
Neuling
Neuling
Beiträge: 2
Registriert: 19. Jul 2015 23:00

Re: Coding with Variance

Beitrag von dat »

I have a non-technique question. Do we need to draw class diagram for this question? I just want to make sure because the question states "Sketch two designs".

m.hosseinian
Windoof-User
Windoof-User
Beiträge: 34
Registriert: 3. Mai 2015 21:28

Re: Coding with Variance

Beitrag von m.hosseinian »

dat hat geschrieben:I have a non-technique question. Do we need to draw class diagram for this question? I just want to make sure because the question states "Sketch two designs".
Assuming this hint:
You do not have to implement the sorting method, but indicate in a _comment_ where you use the comparison operation
I would say we would have had to write two trait skeleton. But still in doubt, _sketch_ is kind of ambiguous in this place!
Unfortunately, none of the officials showed up although, this thread became kind of hot! :-(

Assax
Windoof-User
Windoof-User
Beiträge: 41
Registriert: 2. Dez 2011 10:38

Re: Coding with Variance

Beitrag von Assax »

It was explicitly stated on Thursday by Prof. Eichberg that DRAWING UML will not be part of the exam, however you should be able to read it.

I asked him how we should show our designs then in case of pattern and he said it is to be expected that we could write it in code.

dat
Neuling
Neuling
Beiträge: 2
Registriert: 19. Jul 2015 23:00

Re: Coding with Variance

Beitrag von dat »

Thanks! That is good to know :D

Antworten

Zurück zu „Archiv“