Scala не может вывести правильные аргументы типа - PullRequest
Новая
       52

Scala не может вывести правильные аргументы типа

5 голосов
/ 30 июля 2011

Справочная информация: В настоящее время я пытаюсь настроить универсальную библиотеку графов, которая включает в себя несколько различных алгоритмов поиска (я начал с Дейкстры).Я настроил несколько признаков для представления методов, которые можно найти в определенных типах графиков (например, взвешенные, направленные): 

trait GraphOps[V,E] { ... }
trait WeightedGraphOps[V,E] extends GraphOps[V,E] { ... }
trait DirectedGraphOps[V,E] extends GraphOps[V,E] { ... }
object GraphOps{
  def Dijkstra[V,E,G <: WeightedGraphOps[V,E] with DirectedGraphOps[V,E]](graph:G, start:V) = { ... }
}

В других местах у меня есть класс в качестве конкретной реализации взвешенного,Направленный граф, на котором я хочу запустить алгоритм Дейкстры: 

class GraphMap[T](...)
extends scala.collection.mutable.Map[Position,T]
with WeightedGraphOps[Position,Edge] with DirectedGraphOps[Position,Edge] { ... }

Но когда я пытаюсь проверить это: 

val graph = new GraphMap[Int](...)
val (dist, prev) = GraphOps.Dijkstra(graph, Position(0,0))

Вопрос: Я получаю следующееошибка во время компиляции: error: inferred type arguments [com.dylan.data.Position,Nothing,com.dylan.data.GraphMap[Int]] do not conform to method Dijkstra's type parameter bounds [V,E,G <: com.dylan.data.WeightedGraphOps[V,E] with com.dylan.data.DirectedGraphOps[V,E]]
Мне потребовалось достаточно много времени, чтобы заметить, что мой тип Edge (E) выводится как Nothing, но я не понимаю, почему он не может сделать вывод, что он должен бытьEdge.Почему он не может определить этот параметр типа и как я могу это исправить?

PS Я попытался сделать следующее и заставил его работать, но это кажется ужасно неудобным для того, что должно было быть удобным методом: 

type Helpful = WeightedGraphOps[Position,Edge] with DirectedGraphOps[Position,Edge]
val (dist, prev) = GraphOps.Dijkstra[Position,Edge,Helpful](graph, Position(0,0))

Ответы [ 2 ]

6 голосов
/ 30 июля 2011

Даниэль, вероятно, прав, что существующий логический модуль типа Scala нуждается в более прямой информации, чтобы выяснить, что E должно быть Edge.Кроме того, я понимаю, что вывод типов преднамеренно недооценен, чтобы освободить место для будущих улучшений.

В любом случае, я думаю, что вы можете использовать другой подход к дизайну, который решит проблему вывода типов: используйте тип членов , а не параметров.Ниже я проиллюстрировал, что я имею в виду с помощью автономного кода.Основная идея заключается в том, что типы E и V становятся частью типа GraphOps, но они все еще могут отображаться как параметры типа с помощью уточнения типа , как в методе Dijkstra. 

trait GraphOps { type E; type V }
trait WeightedGraphOps extends GraphOps { }
trait DirectedGraphOps extends GraphOps { }
object GraphOps{
  def Dijkstra[V0, G <: (WeightedGraphOps{type V = V0})
                         with (DirectedGraphOps{type V = V0})]
      (graph:G, start:V0) = { }
}

case class Position(x: Int, y: Int)
case class Edge()

case class GraphMap[T]() extends WeightedGraphOps with DirectedGraphOps {
  type E = Edge
  type V = Position
}

object Test {
  val graph = new GraphMap[Int]( )
  GraphOps.Dijkstra(graph, Position(0,0))
}

Редактировать : Одно из возможных ограничений этого подхода к члену типа заключается в том, что в методе Dijkstra меньше ограничений на параметр типа G.В частности, границы WeightedGraphOps и DirectedGraphOps не обязательно должны иметь одинаковые члены типа E.Я не уверен, как решить эту проблему, не сталкиваясь с проблемой вывода типов, о которой вы изначально сообщали.Одним из подходов будет шаблон в этом вопросе: Почему эти аргументы типа не соответствуют уточнению типа? , но, похоже, компилятор Scala не может с этим справиться.

Edit2 Игнорировать вышеприведенный абзац.Как отметил Дилан в комментариях, для этой ситуации наследование алмазов Scala прекрасно обеспечивает согласованность типа E.Например, следующее компилирует нормально: 

trait GraphOps { type E; type V }
trait WeightedGraphOps extends GraphOps { def f(e: E) }
trait DirectedGraphOps extends GraphOps { def e: E }
object GraphOps{
  def Dijkstra[V0, G <: (WeightedGraphOps{type V = V0}) with (DirectedGraphOps{type V = V0})] (graph:G, start:V0) = {
    graph.f(graph.e)
  }
}
2 голосов
/ 30 июля 2011

Почему это должно быть Edge? Если вы посмотрите на объявление Dijkstra, вы увидите, что ни один из параметров не ссылается на E: (graph:G, start:V). Таким образом, у Scala есть ключ к пониманию того, каким должно быть G, и каким должно быть V. Там нет параметра, ссылающегося на E.

...