generic - scala tuple type
Domando el sistema de tipo Scala (2)
Parece que no entiendo el sistema tipo Scala. Estoy tratando de implementar dos rasgos básicos y un rasgo para que una familia de algoritmos trabaje con ellos. ¿Qué estoy haciendo mal en el siguiente?
Los rasgos base para movimientos y estados; Estos se simplifican para simplemente incluir métodos que exponen el problema.
trait Move
trait State[M <: Move] {
def moves: List[M]
def successor(m: M): State[M]
}
Aquí está el rasgo para la familia de algoritmos que hace uso de lo anterior. No estoy seguro de que esto sea correcto! Puede haber algo de + M / -S involucrado ...
trait Algorithm {
def bestMove[M <: Move, S <: State[M]](s: S): M
}
Movimiento concreto y estado:
case class MyMove(x: Int) extends Move
class MyState(val s: Map[MyMove,Int]) extends State[MyMove] {
def moves = MyMove(1) :: MyMove(2) :: Nil
def successor(p: MyMove) = new MyState(s.updated(p, 1))
}
Estoy en un terreno muy inestable con respecto al siguiente, pero el compilador parece aceptarlo ... Intentando hacer una implementación concreta del rasgo de algoritmo.
object MyAlgorithm extends Algorithm {
def bestMove(s: State[Move]) = s.moves.head
}
Hasta ahora no hay errores de compilación; Se muestran cuando trato de poner todas las partes juntas, sin embargo:
object Main extends App {
val s = new MyState(Map())
val m = MyAlgorithm.bestMove(s)
println(m)
}
Lo anterior arroja este error:
error: overloaded method value bestMove with alternatives:
(s: State[Move])Move <and>
[M <: Move, S <: State[M]](s: S)M
cannot be applied to (MyState)
val m = MyAlgorithm.bestMove(s)
^
Actualización: Cambié el rasgo de algoritmo para usar miembros de tipo abstracto, como se sugiere. Esto resolvió la pregunta como la había formulado, pero la había simplificado demasiado. Se debe permitir que el método MyAlgorithm.bestMove() se llame a sí mismo con la salida de s.successor (m), como esto:
trait Algorithm {
type M <: Move
type S <: State[M]
def bestMove(s: S): M
}
trait MyAlgorithm extends Algorithm {
def score(s: S): Int = s.moves.size
def bestMove(s: S): M = {
val groups = s.moves.groupBy(m => score(s.successor(m)))
val max = groups.keys.max
groups(max).head
}
}
Lo anterior da ahora 2 errores:
Foo.scala:38: error: type mismatch;
found : State[MyAlgorithm.this.M]
required: MyAlgorithm.this.S
val groups = s.moves.groupBy(m => score(s.successor(m)))
^
Foo.scala:39: error: diverging implicit expansion for type Ordering[B]
starting with method Tuple9 in object Ordering
val max = groups.keys.max
^
¿Tengo que pasar a un enfoque que use rasgos de rasgos, también conocido como el patrón de Cake, para que esto funcione? (Solo estoy adivinando aquí; todavía estoy completamente confundido).
Para el código actualizado.
El compilador es muy justo con las quejas. El algoritmo usa una subclase de estado como se indica y el sucesor del estado puede devolver cualquier otra subclase de estado [M]
Puedes declarar clase IntegerOne
trait Abstract[T]
class IntegerOne extends Abstract[Int]
pero el compilador no tiene idea de que todas las instancias de AbstractOne [Int] sean IntegerOne. Se supone que puede haber otra clase que también implementa Abstract [Int]
class IntegerTwo extends Abstract[Int]
Puede intentar utilizar la conversión implícita para convertir desde Abstract [Int] a IntegerOne, pero los rasgos no tienen límites de visión implícitos, ya que no tienen ningún parámetro de valor.
Solución 0
Así que puede volver a escribir su rasgo de algoritmo como una clase abstracta y usar la conversión implícita:
abstract class MyAlgorithm[MT <: Move, ST <: State[MT]] (implicit val toSM : State[MT] => ST) extends Algorithm {
override type M = MT // finalize types, no further subtyping allowed
override type S = ST // finalize types, no further subtyping allowed
def score(s : S) : Int = s.moves.size
override def bestMove(s : S) : M = {
val groups = s.moves.groupBy( m => score(toSM ( s.successor(m)) ) )
val max = groups.keys.max
groups(max).head
}
}
implicit def toMyState(state : State[MyMove]) : MyState = state.asInstanceOf[MyState]
object ConcreteAlgorithm extends MyAlgorithm[MyMove,MyState]
object Main extends App {
val s = new MyState(Map())
val m = ConcreteAlgorithm.bestMove(s)
println(m)
}
Hay dos inconvenientes en esta solución
- utilizando la conversión implícita con asInstanceOf
- tipos de atado
Usted puede extinguir primero como el costo de atar otro tipo.
Solución 1
Deje usar el algoritmo como única fuente de parametrización de tipo y reescriba la estructura de tipo en consecuencia
trait State[A <: Algorithm] { _:A#S =>
def moves : List[A#M]
def successor(m : A#M): A#S
}
trait Algorithm{
type M <: Move
type S <: State[this.type]
def bestMove(s : S) : M
}
En ese caso, su MyAlgorithm se puede utilizar sin reescribir
trait MyAlgorithm extends Algorithm {
def score(s : S) : Int = s.moves.size
override def bestMove(s : S) : M = {
val groups = s.moves.groupBy(m => score(s.successor(m)))
val max = groups.keys.max
groups(max).head
}
}
Usándolo:
class MyState(val s : Map[MyMove,Int]) extends State[ConcreteAlgorithm.type] {
def moves = MyMove(1) :: MyMove(2) :: Nil
def successor(p : MyMove) = new MyState(s.updated(p,1))
}
object ConcreteAlgorithm extends MyAlgorithm {
override type M = MyMove
override type S = MyState
}
object Main extends App {
val s = new MyState(Map())
val m = ConcreteAlgorithm.bestMove(s)
println(m)
}
Vea un ejemplo de uso más abstracto y complicado para esta técnica: Scala: tipos abstractos vs genéricos
Solucion 2
También hay una solución simple para su pregunta, pero dudo que pueda resolver su problema. Eventualmente, se quedará atascado en una inconsistencia de tipo nuevamente en casos de uso más complejos.
Simplemente haga que MyState.successor devuelva este tipo de this.type lugar de State[M]
trait State[M <: Move] {
def moves : List[M]
def successor(m : M): this.type
}
final class MyState(val s : Map[MyMove,Int]) extends State[MyMove] {
def moves = MyMove(1) :: MyMove(2) :: Nil
def successor(p : MyMove) = (new MyState(s.updated(p,1))).asInstanceOf[this.type]
}
otras cosas no han cambiado
trait Algorithm{
type M <: Move
type S <: State[M]
def bestMove(s : S) : M
}
trait MyAlgorithm extends Algorithm {
def score(s : S) : Int = s.moves.size
override def bestMove(s : S) : M = {
val groups = s.moves.groupBy(m => score(s.successor(m)))
val max = groups.keys.max
groups(max).head
}
}
object ConcreteAlgorithm extends MyAlgorithm {
override type M = MyMove
override type S = MyState
}
object Main extends App {
val s = new MyState(Map())
val m = ConcreteAlgorithm.bestMove(s)
println(m)
}
Preste atención al modificador final de la clase MyState. Se asegura de que la conversión comoInstanceOf [this.type] sea correcta. El compilador de Scala puede calcular que la clase final mantiene siempre este tipo de this.type pero todavía tiene algunas fallas.
Solucion 3
No es necesario vincular el algoritmo con el estado personalizado. Mientras el algoritmo no use una función de estado específica, puede escribirse más simple sin ejercicios de delimitación de tipo.
trait Algorithm{
type M <: Move
def bestMove(s : State[M]) : M
}
trait MyAlgorithm extends Algorithm {
def score(s : State[M]) : Int = s.moves.size
override def bestMove(s : State[M]) : M = {
val groups = s.moves.groupBy(m => score(s.successor(m)))
val max = groups.keys.max
groups(max).head
}
}
Este simple ejemplo no me viene a la mente rápidamente porque asumí que la vinculación a diferentes estados es obligatoria. Pero a veces solo una parte del sistema debería parametrizarse explícitamente y puede evitar una complejidad adicional con él
Conclusión
El problema discutido refleja un montón de problemas que surgen en mi práctica muy a menudo.
Hay dos propósitos en competencia que no deben excluirse entre sí, sino hacerlo en Scala.
- extensibilidad
- generalidad
Primero significa que puede construir un sistema complejo, implementar alguna realización básica y ser capaz de reemplazar sus partes una por una para implementar una realización más compleja.
En segundo lugar le permite definir un sistema muy abstracto, que puede ser utilizado para diferentes casos.
Los desarrolladores de Scala tuvieron una tarea muy desafiante para crear un sistema de tipos para un lenguaje que puede ser tanto funcional como orientado a objetos, a la vez que se limita al núcleo de implementación jvm con enormes defectos como el borrado de tipos. La anotación de tipo Co / Contra-varianza dada a los usuarios es insuficiente para expresar relaciones de tipos en un sistema complejo
Tengo mis momentos difíciles cada vez que encuentro un dilema de extensibilidad y generalidad para decidir qué compensación aceptar.
No me gustaría utilizar un patrón de diseño, sino declararlo en el idioma de destino. Espero que Scala me dé esta habilidad algún día.
Usted declara MyAlgorithm#bestMove explícitamente como tomando un parámetro State[Move] , pero dentro de Main está intentando pasarle un MyState , que es un State[MyMove] no un State[Move] .
Tienes un par de opciones para resolver esto. Uno sería no restringir los tipos en MyAlgorithm :
object MyAlgorithm extends Algorithm {
def bestMove[M <: Move, S <: State[M]](s: S) : M = s.moves.head
}
Desafortunadamente, la inferencia de tipos de Scala no es lo suficientemente inteligente como para resolver estos tipos por usted, por lo que en el sitio de la llamada, debe declararlos, haciendo que la llamada a MyAlgorithm#bestMove aspecto:
val m = MyAlgorithm.bestMove[MyMove, MyState](s)
Otra opción utiliza miembros de tipo abstracto del rasgo de Algorithm :
trait Algorithm {
type M <: Move
type S <: State[M]
def bestMove(s: S): M
}
Y resolver los tipos abstractos en la implementación concreta:
object MyAlgorithm extends Algorithm {
type M = MyMove
type S = MyState
def bestMove(s: S) : M = s.moves.head
}
Luego, el sitio de la llamada vuelve a su versión original, sin mencionar los tipos:
val m = MyAlgorithm.bestMove(s)
Es posible que desee mantener MyAlgorithm sin conocer los tipos reales, y dejar la determinación de esos tipos a los ''clientes'' de ese objeto, en cuyo caso, cambie el objeto a un rasgo:
trait MyAlgorithm extends Algorithm {
def bestMove(s: S) : M = s.moves.head
}
Luego, en su clase principal, MyAlgorithm una instancia de un MyAlgorithm con los tipos concretos:
val a = new MyAlgorithm {
type M = MyMove
type S = MyState
}
val m = a.bestMove(s)
Tu comentario "Puede que haya algunas cosas de + M / -S involucradas" fue una buena suposición, pero no funcionará para ti aquí. Puede esperar que el modificador de tipo covariante "+" pueda ayudar aquí. Si hubiera declarado el parámetro de tipo en State como
State[+M]
Esto indicaría que el State[M] <:< State[N] si M <:< N . (lea <:< como "es un subtipo de"). Entonces no tendría ningún problema en pasar a un estado [MyMove] donde se esperaba un estado [Move]. Sin embargo, no puede usar el modificador covariante en M aquí porque aparece en la posición contravariante como un argumento a la función sucesora.
¿Por qué es esto un problema? Su declaración de sucesor dice que tomará una M y devolverá un Estado. La anotación covariante dice que un Estado [M] también es un Estado [Cualquiera]. Así que deberíamos permitir esta asignación:
val x : State[Any] = y : State[MyMove]
Ahora bien, si tenemos un State[Any] , entonces x.successor es de qué tipo? Any => MyMove . Lo cual no puede ser correcto, ya que su implementación espera un MyMove , no un Any