When using type classes, how to deal with object in different ways?
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?
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
}
val x: Set[(A, A)] = ...
(x: Graph[_, _]).map(...)
seems to be the best you can do if you want the names to be the same.
As you point out, that's not what you want. This should work better:
object Graph {
def map[G, V](graph: G)(f: V => V)(implicit instance: Graph[G, V]) = ...
}
val x: Set[(A, A)] = ...
Graph.map(x)(f)
// but note that the type of argument of f will often need to be explicit, because
// type inference only goes from left to right, and implicit arguments come last
Note that you can only let f to be V => V and not V => V1 . Why? Imagine that you have implicit g1: Graph[SomeType, Int] , but not implicit g2: Graph[SomeType, String] . What could Graph.map(_: SomeType)((_: Int).toString) return then? This problem can be avoided by requiring G to be a parametrized type:
trait Graph[G[_]] {
def nodes[A](g: G[A]): Set[A]
def adjacent[A](g: G[A], n1: A, n2: A): Boolean
}
object TupleSetGraph{
type SetOfPairs[A] = Set[(A,A)]
implicit def ts2graph: Graph[SetOfPairs] = new Graph[SetOfPairs] {
def nodes[A](g: Set[(A, A)]): Set[A] = g flatMap (t => Set(t._1,t._2))
def adjacent[A](g: Set[(A, A)], n1: A, n2: A): Boolean = g.contains((n1,n2)) || g.contains((n2,n1))
}
}
then you have
object Graph {
def map[G[_], V, V1](graph: G[V])(f: V => V1)(implicit instance: Graph[G]) = ...
}
If you are using type classes, then you can do something like this:
implicitly[TypeClass].map(...)
If you are using view bounds, then Alexey's answer is correct:
(...: ViewBound).map(...)
上一篇: 统计电话的数量