textual - ¿Por qué la inferencia de tipo de Scala no es tan poderosa como la de Haskell?

tecnicas de inferencia de tipos

Question

El motor de inferencia tipo de Haskell es mucho más poderoso que el de Scala. En Haskell rara vez tengo que escribir explícitamente los tipos, mientras que en Scala los tipos solo se pueden inferir en expresiones, pero no en definiciones de métodos.

Por ejemplo, consulte el siguiente fragmento de código Haskell:

size xs = loop xs 0
  where
    loop [] acc = acc
    loop (_ : xs) acc = loop xs (acc+1)

Devuelve el tamaño de una lista. El compilador de Haskell puede reconocer qué tipos se utilizan y cuál es la definición de la función. El código equivalente de Scala:

def size[A]: List[A] => Int = xs => {
  def loop: (List[A], Int) => Int = {
    case (Nil, acc) => acc
    case (_ :: xs, acc) => loop(xs, acc+1)
  }
  loop(xs, 0)
}

O con definiciones de métodos:

def size[A](xs: List[A]) = {
  def loop(xs: List[A], acc: Int): Int = xs match {
    case Nil => acc
    case _ :: xs => loop(xs, acc+1)
  }
  loop(xs, 0)
}

Mi pregunta es: ¿por qué no puedo escribirlos de la siguiente manera?

def size = xs => {
  def loop = {
    case (Nil, acc) => acc
    case (_ :: xs, acc) => loop(xs, acc+1)
  }
  loop(xs, 0)
}

Una vez más con las definiciones de métodos:

def size(xs) = {
  def loop(xs, acc) = xs match {
    case Nil => acc
    case _ :: xs => loop(xs, acc+1)
  }
  loop(xs, 0)
}

¿Es porque nadie lo ha implementado todavía? ¿El sistema de tipos de Scala no es tan poderoso como se necesita para este caso? ¿O hay otras razones?

Answer 1

La razón principal es que el sistema de tipos de Scala permite subtipos, que el algoritmo de inferencia de tipo Hindley-Milner no admite.

Haskell no tiene sub-tipado, por lo que el algoritmo funciona mucho mejor allí, aunque muchas extensiones de sistema de tipo popular compatibles con GHC hacen que la inferencia de tipo vuelva a fallar, lo que le obliga a proporcionar firmas de tipo explícitas para algunas expresiones.

Al final, es una compensación entre la potencia del sistema de tipo y la cantidad de inferencia de tipo que se puede hacer. Scala y Haskell simplemente han hecho diferentes intercambios.

Answer 2

Otra cosa que no funciona bien con la inferencia de tipo Hindley-Milner es la sobrecarga de métodos y las características relacionadas, como argumentos predeterminados y varargs. Esa es la razón por la que es tan difícil escribir cosas como zipWithN en Haskell (que es trivial en Scala).

Answer 3

Supongo que las razones principales ya han sido dadas, pero creo que esta cita del creador de Scala, Martin Odersky, es particularmente informativa,

La razón por la que Scala no tiene inferencia de tipo Hindley / Milner es que es muy difícil combinarla con características como la sobrecarga (la variante ad-hoc, no las clases de tipo), la selección de registros y la subtipificación. No digo que sea imposible: existen varias extensiones que incorporan estas características; de hecho, he sido guitly de algunos de ellos yo mismo. Solo digo que es muy difícil hacer que esto funcione bien en la práctica, donde uno necesita expresiones de tipo pequeño y buenos mensajes de error. Tampoco es un caso cerrado: muchos investigadores están trabajando para ampliar los límites aquí (por ejemplo, en el FML de Remy). Pero en este momento es una compensación de mejor tipo de referencia vs mejor soporte para estas características. Puedes hacer el intercambio en ambos sentidos. El hecho de que quisiéramos integrar con Java inclinó la balanza a favor de la subtipificación y de Hindley / Milner.

Fuente: comentario en el post Universal Type Inference es una mala cosa .

Answer 4

hammar dio la razón más grande. Aquí hay otros dos:

• Scala usa tipos para resolver nombres

Considerar

def foo(x) = x.a + x.b

¿Cómo podría Scala inferir el tipo de argumento? ¿Debería buscar todas las clases con un campo a y b ? ¿Qué pasa si hay más de 1? En Haskell

foo x = (a x) + (b x)

los nombres de registro son únicos, lo que presenta sus propios problemas, pero significa que siempre se puede inferir a qué tipo de registro se hace referencia.

• Para su ejemplo: las expresiones de case en Scala pueden ser heterogéneas

En Scala, el tipo de objeto que se empareja se puede utilizar como parte de la coincidencia o para decidir cómo se debe hacer la coincidencia. Entonces, incluso si todos los constructores en el case son para List , es posible que desee pasarle algo que no sea una lista y hacer que falle.