Playing with Scala 3: OO, Traits, and Views

OO

Look at graph classes my previous post:

class Node (val label:String) {
var transitions: List[Arc] = Nil
var previous: Node = _
var weight= Float.PositiveInfinity
var visited = false
...

and

class Arc(var start: Node, var end: Node) {
var weight: Float = _
...
Don't you feel that something doesn't really fit? What are previous, visited, and weight are doing in Node? And weight in Arc?

Those properties doesn't really belong to a generic Node or Arc, they're specific for our algorithm. So, why having them there? Let's put those attributes on special cases of Node and Arc: DfsNode and DfsArc. But wait! Putting weight in both doesn't seem right either... we're defining the same thing twice! Weight is some kind of "cross-cutting" attribute.

Traits

Luckily modern OO languages had a very elegant way of solving this kind of problems by means of traits (usually are described as "interfaces with implementation" but a very powerful concept), so let's define our weight as a trait:

trait Weighted {
var weight= Float.PositiveInfinity
}

So we can clean our Node and Arc classes:

class Node(val label:String) {
var transitions: List[Arc] = Nil

override def toString()= {
label
}

def --> (end: Node):Arc={
transitions = new Arc(this,end) :: transitions
transitions.head
}
}

class Arc(var start: Node, var end: Node) {

override def toString()= {
start.label+"-->"+end.label
}
}

Now they look useful for any graph application, and we can define our particular versions for the Dfs algorithm:

class DfsNode (label:String) extends Node(label) with Weighted {
var previous: DfsNode = _
var visited = false

override def toString()= {
super.toString+" w:"+weight+" p:"+previous
}
}

class Arc(var start: Node, var end: Node) {
override def toString()= {
start.label+"-->"+end.label
}
}

And I just need to change the signatures of the functions of the algorithm:

object Dijkstra {

def shortestPath(graph:Set[DfsNode], start: DfsNode, end: DfsNode) = {
var unvisited=graph
start.weight=0
while (!unvisited.isEmpty) {
val vertx=min(unvisited)
vertx.transitions.map(improveDistance(_))
unvisited=unvisited-vertx
}
}

def improveDistance(a:DfsArc) ={
if (a.start.weight+a.weight< a.end.weight) {
a.end.weight=a.start.weight+a.weight
a.end.previous=a.start
}
}

def min(nodes: Set[DfsNode]): DfsNode = {
nodes.reduceLeft((a:DfsNode,b:DfsNode)=>if (a.weight<b.weight) a else b )
}

def pathTo(end:DfsNode):List[DfsNode] = {
if (end == null)
Nil
else
end :: pathTo(end.previous)
}
}

What? It doesn't compile! node.transitions returns a list of Nodes and not DfsNodes! Argh! We've been bitten by the static typing! ("Ha-ha" will shout the Dynamic typing Nelson). I could use a .asInstanceOf[type] everywhere (like a Java cast) but it looks like a kludge and you have to put everywhere! There must be a better solution, after all, Scala is supposed to look elegant, right?

Views (implicit conversions)

Scala has a very interesting way of dealing with that kind of problem: by creating views using implicit conversions, we can convert from one type to other, the compiler will insert the appropriate call when needed. So I defined a conversion from Arc to DfsArc and Node to DfsNode:

object Implicits {
implicit def node2DfsNode(node:Node):DfsNode={
if (node.isInstanceOf[DfsNode])
node.asInstanceOf[DfsNode]
else {
var dfsNode=new DfsNode(node.label)
dfsNode.transitions=node.transitions
dfsNode
}
}

implicit def arc2DfsArc(arc:Arc):DfsArc={
if (arc.isInstanceOf[DfsArc])
arc.asInstanceOf[DfsArc]
else {
new DfsArc(arc.start,arc.end)
}
}
}

And now, everything will happly compile. The only caveat is as I defined the method --> returning an Arc and arc2DfsArc creating a new instance if I pass an Arc, the use of n1-->n2 weight=2 sets the weight in a new object and not in the object in the transitions collection. I'm sure there's a better solution, but meanwhile if we overrride the --> method in DfsNode will work:
def --> (end: DfsNode):DfsArc={
transitions = new DfsArc(this,end) :: transitions
transitions.head.asInstanceOf[DfsArc]
}

(Let me know if you want the full code posted)