When using type classes, how to deal with object in different ways?

Question

Suppose I have a type class Graph[G,V] which states that an object of type G is also a graph with vertices of type V.

Now I have an implicit that lets me treat sets of pairs of type A as a graph with vertices of type A (not being able to express unconnected vertices...). I can use the implicit by importing the following object's scope.

object TupleSetGraph{
  implicit def ts2graph[A]: Graph[Set[(A,A)],A] = new Graph[Set[(A,A)],A] {
    def nodes(g: Set[(A, A)]): Set[A] = g flatMap (t => Set(t._1,t._2))
    def adjacent(g: Set[(A, A)], n1: A, n2: A): Boolean = g.contains((n1,n2)) || g.contains((n2,n1))
  }
}

Suppose I also want to be able to map the content of the vertices, thus being able to do the following:

(_: Set[(A,A)]).map((_: A => B)): Set[(B,B)]

But there is already a map defined on Set. How to deal with the problem that the same data structure can be seen as the same thing (something having a map function) in different ways?

Answer 1

Sketching a possible solution :

Put the map operation in an auxiliary trait

say GraphOps (that could be Graph itself, but map signature will probably be too complex for that)

case class GraphOps[G](data: G) { def map...}

Making it easy to get the GraphOps :

object Graph {
   def apply[G](data: G) = GraphOps(data)
}

With that, the call will be

Graph(set).map(f) 

apply could be made implicit, but I'm not sure I want to do that (and if I did, I'm not sure it would find map properly).

Variant. Have the graph in GraphOps

we can also do

case class GraphOps[G,V](data: G, graph: Graph[G,V])

and

object Graph {
   def apply[G,V](data: G)(implicit graph: Graph[G,V]) = GraphOps(data, graph)
}

The good point of that is that vertex type V is available in GraphOps

Defining the map operation

The signature you want is complex, with Set[(A,A)] returning a Set[(B,B)], but other graph implementations returning something completely different. This is similar to what is done in the collection library.

We may introduce a trait CanMapGraph[From, Elem, To], akin to CanBuildFrom

trait CanMapGrap[FromGraph, FromElem, ToGraph, ToElem] {
  def map(data: FromGraph, f: FromElem => ToElem): ToGraph
}

(probably you would change this to have more elementary operations than map, so that it may be used for different operations, as done with CanBuildFrom)

Then map would be

case class GraphOps[G](data: G) {
  def map[A,B](f: A, B)(implicit ev: CanMapFrom[G, A, B, G2]) : G2 =
    ev.map(data, f)
}

You can define

implicit def mapPairSetToPairSet[A, B] = 
  new CanMapGraph[Set[(A,A)], A, Set[(B,B)], B] {
    def map(set: Set[(A,A)], f: A => B) = set.map{case (x, y) => (f(x), f(y))}
  } 

And then you do

val theGraph = Set("A" -> "B", "BB" -> "A", "B" -> "C", "C" -> "A")
Graph(theGraph).map(s: String -> s(0).toLower)
res1: Set[(Char, Char)] = Set((a,b), (b,a), (b,c), (c,a))

A problem with that is that the type of the vertices is not known in the first argument list, the one for f, so we have to be explicit with s: String.

With the alternative GraphOps, where we get the vertex type early, A is not a parameter of Map, but of GraphOps, so it is known from the start and does not need to be explicit in f. It you do it that way, you may want to pass the graph to method map in CanMapGraph.

With the first solution, it is still easy to give the graph to the CanMapGraph.

implicit def anyGraphToSet[G,V,W](implicit graph: Graph[G,V]) 
  = new CanMapFrom[G, V, Set[(W,W)], W] {
    def map(data: G, f: V => W) = 
      (for {
         from <- graph.nodes(data)
         to <- graph.nodes(data)) 
         if graph.adjacent(data, from, to) }
       yield (from, to)).toSet
  }