7

Graph[G,V]型のオブジェクトが型のG頂点を持つグラフでもあることを示す型クラスがあるとしますV。

Aこれで、タイプのペアのセットをタイプの頂点を持つグラフとして扱うことができる暗黙的なものができましたA（接続されていない頂点を表現できません...）。次のオブジェクトのスコープをインポートすることで、暗黙を使用できます。

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))
  }
}

また、頂点のコンテンツをマッピングして、次のことができるようにしたいとします。

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

しかし、にはすでにmap定義されていSetます。同じデータ構造が異なる方法で同じもの（map機能を持つもの）と見なされる可能性があるという問題にどのように対処しますか？

4

3 に答える 3

3

考えられる解決策のスケッチ：

マップ操作を補助特性に入れます

言うGraphOps（Graphそれ自体かもしれませんが、マップの署名はおそらくそれには複雑すぎるでしょう）

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

簡単に入手できるようにするGraphOps：

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

それで、呼び出しは

Graph(set).map(f)

apply暗黙的にすることもできますが、それを実行したいかどうかはわかりません（実行した場合、マップが適切に検出されるかどうかはわかりません）。

変異体。GraphOpsにグラフを作成する

私たちもできる

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

と

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

その良い点は、頂点タイプVがGraphOpsで利用できることです。

マップ操作の定義

必要な署名は複雑で、Set [（A、A）]はSet [（B、B）]を返しますが、他のグラフ実装はまったく異なるものを返します。これは、コレクションライブラリで行われることと似ています。

CanBuildFromに似た特性CanMapGraph[From、Elem、To]を導入する場合があります

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

（おそらく、これをマップよりも多くの基本操作を持つように変更して、で行われるように、さまざまな操作に使用できるようにしますCanBuildFrom）

次に、マップは

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)
}

あなたは定義することができます

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))}
  }

そして、あなたは

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))

それに関する問題は、頂点のタイプが最初の引数リスト（fの引数リスト）で不明であるため、s：Stringで明示する必要があることです。

GraphOps頂点タイプを早期に取得する代替案でAは、Mapのパラメーターではなく、のパラメーターであるGraphOpsため、最初から既知であり、で明示的にする必要はありませんf。そのようにすると、グラフをのメソッドに渡すことができmapますCanMapGraph。

最初の解決策では、グラフをに与えるのは簡単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
  }
于 2011-10-25T16:11:39.253 に答える
1 
val x: Set[(A, A)] = ...
(x: Graph[_, _]).map(...)

名前を同じにしたい場合は、できる限り最善のようです。

あなたが指摘するように、それはあなたが望むものではありません。これはうまくいくはずです：

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

あなたはそうすることしかできず、そうすることはできないことに注意しfてV => VくださいV => V1。なんで？implicit g1: Graph[SomeType, Int]あなたが持っているが、持っていないことを想像してみてください implicit g2: Graph[SomeType, String]。それでは何がGraph.map(_: SomeType)((_: Int).toString)返ってくるでしょうか？Gこの問題は、パラメータ化されたタイプである必要があることで回避できます。

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))
  }
}

その後、あなたは持っています

object Graph {
  def map[G[_], V, V1](graph: G[V])(f: V => V1)(implicit instance: Graph[G]) = ...
}
于 2011-10-25T13:21:01.330 に答える
0

型クラスを使用している場合は、次のようなことができます。

implicitly[TypeClass].map(...)

ビュー境界を使用している場合、Alexeyの答えは正しいです。

(...: ViewBound).map(...)
于 2011-10-25T16:55:59.840 に答える