Crear un tipo de gráfico paramétrico en Scala

Me gustaría crear una jerarquía de tipos genéricos para representar gráficos. En particular, me gustaría tener las clases Graph y Node, y quiero que para cada tipo de gráfico, haya un tipo de nodo correspondiente y si creo una función genérica para manipular gráficos, quiero que esta función use el nodo actual. tipo. Un ejemplo que he intentadoCrear un tipo de gráfico paramétrico en Scala

trait GNode[Graph] 
{ 
... functions to get edges from this vertex, etc. ... 
} 

trait Graph 
{ 
    type Node <: GNode[Graph] 
} 

def dfs[G <: Graph](g : G, nodeAction : G#Node => Unit) = ... code ...

pero esto no funcionó, porque cuando lo hice

class ConcreteGraph extends Graph 
{ 
    class Node extends GNode[ConcreteGraph] { ... } 
}

la función DFS no aceptaría una función del tipo ConcreteGraph#Node=>Unit como nodeAction, pero sólo AnyRef=>Unit o GNode[ConcreteGraph]=>Unit.

Para ser más claro, si lo hice en C++, que haría algo así como

template <class T> struct graph_traits; 
template <> struct graph_traits<concrete_graph> 
{ typedef concrete_graph::node node_type; } 

template <class G> 
void dfs(const G& g, boost::function<void(
      const graph_traits<G>::node_type&)> action) { ... }

Fuente

2009-02-11 jpalecek

Un muy buen ejemplo de un gráfico de la estructura extensible está en http://www.scala-lang.org/node/124

yo te tengo formas de escribe el tuyo Tenga en cuenta que en todos los casos hubo algunos cambios de tipo necesarios, es decir, el parámetro de tipo GNode debe ser covariante, y ConcreteGraph debe escribirse con una clase de nodo distinta y un tipo vinculado para el nodo.

Una vez hecho esto, la primera forma de escribir dfs es convertirlo en un método (puede ser definitivo si desea evitar la sobrecarga del envío virtual).

trait GNode[+Graph] { 
//... functions to get edges from this vertex, etc. ... 
} 

trait Graph { 
    type Node <: GNode[Graph] 

    def dfs(nodeAction : Node => Unit) = print("dfsing!") 
} 

class ConcreteGraph extends Graph { 
    class CGNode extends GNode[ConcreteGraph] 
    type Node <: CGNode 
} 

new ConcreteGraph dfs {node => println("foo")}

La segunda, la DFS y no un método, parece requerir sólo un poco de insinuación de tipo extra para usarlo.

def dfs[G <: Graph](graph : G, nodeAction : G#Node => Unit) = print("dfsing!") 

dfs[ConcreteGraph](new ConcreteGraph, {node => println("foo")})

La tercera manera es con un dfs curried. Debido a la forma en que funciona la inferencia de tipos de Scala, que en realidad se traduce en una interfaz más limpia

def dfs[G <: Graph](graph : G)(nodeAction : G#Node => Unit) = print("dfsing!") 

dfs(new ConcreteGraph){node => println("foo")}

Fuente

2009-02-11 15:35:29

Gracias. Sin embargo, no estoy seguro de por qué tendría que hacer clase CGNode y escribir Nodo en ConcreteGraph. Creé un pequeño ejemplo: http://snipt.org/vpk y me parece funcional – jpalecek

Y otro: en este ejemplo, ¿puedo restringir dfs a esos tipos G, cuyo tipo de Nodo está <: Ordenado o algo así? – jpalecek

no veo por qué todos estos parámetros son necesarios. Las clases internas en Scala (a diferencia de Java) tienen tipos que dependen de la instancia específica del objeto externo. En particular:

trait Graph { 
    trait Node 
    def dfs(n: Node) = println("DFSing!") 
} 

val graphA = new Graph {} 
val nodeA = new graphA.Node {} 
val graphB = new Graph {} 
val nodeB = new graphB.Node {} 
graphA.dfs(nodaA) // prints "DFSing!" 
graphB.dfs(nodeB) // prints "DFSing!" 
graphA.dfs(nodeB) // type mismatch; found: graphB.Node required: graphA.Node 
graphB.dfs(nodeA) // type mismatch; found: graphA.node required: graphB.Node

Por supuesto, no se puede definir DFS fuera del gráfico si quiere depender de tipos dependientes.

Fuente

2009-02-11 19:38:27

Crear un tipo de gráfico paramétrico en Scala

Respuesta

Cuestiones relacionadas