Using traits as a refactoring tool

Question
1

I have not used traits before in my Scala journey. And I wonder whether I could use them to solve a certain refactoring problem. I have a class Graph which represents a collection of vertices and edges between the vertices. There are many feature which graphs ought to support, e.g., various shortest path algorithms, Bellman-Ford, Dijkstra, Floyd-Warshall, and also isomorphism algorithms, matchings, walks and searches (BFS, DFS). I don’t really want to put all that into a single source file, as the file would be huge. Can I implement each “graph feature” in a separate trait? and somehow mix them all in together? Each trait would both need to get mixed-in to the Graph class, but the code implementing the trait would need to be able to take advantage of the fact that this is a Graph, i.e., has vertices, edges, adjacency mapping etc. It seems to me that each trait needs to inherit from Graph and also be inherited by Graph. If I implement this all between the {} of the Graph class definition, it will work, but as I said, the implementation will be huge, and be begging for refactoring.

I don’t understand how to correctly represent this using the Scala object system.

2

So with a bit of experimentation the following seems to compile. It appears like the classes can be defined among many files, and as long as they are defined somewhere then everything compiles, and at least my tests pass. Whether it is a good idea to abuse traits for this type of refactoring however, is not clear to me.

// in file1.scala
case class Edge[A](src: A, dst: A) {
  ...
}

abstract class ProtoGraph[A](val Vertices: Set[A], val Edges: Set[(A, A)]) {
  ... }

case class Graph[A](override val Vertices: Set[A], override val Edges: Set[(A, A)])
    extends ProtoGraph[A](Vertices, Edges)
      with Matchings[A]
      with BellmanFord[A] {
}

And then the mix-ins

// in file2.scala
trait BellmanFord[A] extends ProtoGraph[A] {
... }

and also

// in file3.scala

trait Matchings[A] extends ProtoGraph[A] {
...
}
3

It seems that since Scala is a superset of java and since in java it is simple matter structure such code using various OOP techniques you should be able to to do the same in Scala. ( of course I am still a Scala novice :slight_smile: )
Could you put each feature into its own little object and them import the objects into your main-class that exercises the functionality ?

4

Yes, you definitely don’t want to put all these algorithms into a single file. There are many ways to split code into multiple classes.

I should mention I don’t see the need for graph algorithms to be part of a graph. A graph is just a collection of vertices and edges. Graph algorithms can simply have a method that takes a graph (and other things) and returns a result.

I think when you talk of traits to mix in, you mean something like:

trait Window

trait HasTitle extends Window

trait HasScrollbar extends Window

trait HasMenu extends Window

class WindowWithFeatures extends Window with HasTitle with HasScrollbar

class WindowWithMoreFeatures extends Window with HasTitle with HasScrollbar with HasMenu

That is a useful approach if you have a base type (Window) from which you want to derive a bunch of subtypes with varying capabilities, like different types of windows. In principle, you can do that for graphs, but I’m not sure it is a good fit - as I said, algorithms don’t need to be part of a graph. If you ever want to have subtypes of graph, I would expect them to be for fundamental properties such as directed graph, undirected graph, etc.

Inheritance is primarily a tool to create different related types. If you don’t need different types, but only want to divide your code, you probably don’t want inheritance. Instead, create separate types that use each other as fields or method arguments.

5

In general, the data type should be abstracted, and the algorithms should be concrete. An algorithm which can apply to any implementation can work with the data trait, and an algorithm which needs a specific implementation can be an instance method of that implementation class. For example, look at how the collection types in the Scala standard library are implemented. Roughly, you have a Seq trait for sequential collections, a Map trait for maps, and so on. A rough sketch:

trait Graph[A] {
  def vertices: Set[A]
  def edges: Set[(A, A)]

  def shortestPathDijkstra(a1: A, a2: A): Seq[A] = {
    // Implement here or call out to a helper method in a companion object
  }
}

...

// `MyGraph` now has `shortestPathDijkstra`
case class MyGraph[A](
  vertices: Set[A],
  edges: Set[(A, A)]
) extends Graph[A]

You can implement the algorithms directly in the trait or the implementation classes, or you can call out to helpers. The helpers can be just static methods in companion objects. Principle of least power applies: see http://www.lihaoyi.com/post/StrategicScalaStylePrincipleofLeastPower.html#published-interfaces

6

I think others have covered typical best practice – you should lift the abstractions up to traits, and put the implementations in concrete classes that you mix in. But just to answer your specific question:

You can do this with “self-types”. Say that Vertices and Edges were classes that are needed for Graph, and they in turn need to inherit Graph. You could declare them like this:

trait Vertices { self: Graph => ... }
trait Edges { self: Graph => ... }
trait Graph extends Vertices with Edges { ... }

Those self declarations mean “I can only be instantiated if I am mixed into a class that also mixes in Graph”. I don’t think I’ve ever used this for circular dependencies per se, but I believe it would work.

(Note that circular dependencies are dangerous, in part because they can cause your compile times to explode if you over-use them.)

Oh, and there is absolutely nothing wrong, or even unusual, in having a class inherit from a bunch of traits defined in other files. So the solution you came up with is totally reasonable.

Finally, I’ll note that I might implement this stuff in terms of typeclasses (or even plain old functions) instead of inheritance – there’s a well-known tendency to wind up with multiplicative explosion of complexity as you add more and more features via inheritance. But there’s no one true answer here: there are a lot of legitimate ways to break this down.

1 Like