¿Por qué Haskell no puede evitar la evaluación repetida sin la restricción de monomorfismo?

Question

¿Por qué Haskell no puede evitar la evaluación repetida sin la restricción de monomorfismo?

#1 de Karl Bielefeldt (10 votos)

14

Acabo de terminar learnyouahaskell el otro día, y estaba tratando de entender la Restricción de Monomorfismo, tal como lo describe el Wiki de Haskell . Creo que entiendo cómo el MR puede evitar evaluaciones repetidas, pero no logro ver por qué esas evaluaciones repetidas no se pueden evitar por medios mucho más directos.

El ejemplo específico que tengo en mente es el que usa la wiki:

f xs = (len,len)
  where
    len = genericLength xs

donde genericLength es del tipo Num a => [b] -> a .

Obviamente, genericLength xs solo se debe calcular una vez para evaluar (len,len) , ya que es la misma función con los mismos argumentos. Y no necesitamos ver ninguna invocación de f para saberlo. Entonces, ¿por qué Haskell no puede hacer esta optimización sin introducir una regla como la MR?

La discusión en esa página wiki me dice que tiene algo que ver con el hecho de que Num es una clase de tipos en lugar de un tipo concreto, pero aun así, ¿no debería ser obvio en tiempo de compilación que una función pura? devolvería el mismo valor, y por lo tanto el mismo tipo concreto de Num, cuando se le den los mismos argumentos dos veces?

optimization haskell type-systems

pregunta Ixrec 06.05.2015 - 21:50

1 respuesta

Lea otras preguntas en las etiquetas optimization haskell type-systems

Cómo hacer pruebas de API externa (blackbox) TDD con SQL y funciones de manipulación de datos

score 10 · Accepted Answer

Es el mismo nombre de función, con los mismos argumentos, pero potencialmente diferentes tipos de retorno e implementaciones, porque es polimórfico. Eso significa que si se llama en un contexto que espera un tipo de retorno (Int, MyWeirdCustomNumType) , tiene que evaluarlo dos veces, porque la implementación de (+) en Int es completamente diferente de la implementación de (+) en MyWeirdCustomNumType . Debe ejecutar un código físicamente diferente en algún momento.

Por eso es importante que Num sea una clase de tipo. Significa que tienes diferentes implementaciones para diferentes tipos. También significa que si f está en una biblioteca, no sabe en tiempo de compilación todas las combinaciones de tipos que podría necesitar devolver.

Entonces, sí, necesitas ver las invocaciones de f para saber qué tipos de devolución usar. La mayoría de las veces, se espera que sean iguales, por lo que ponen la restricción de monomorfismo en forma predeterminada. Puede desactivarse para las raras ocasiones en que no lo haga. En la práctica, los programadores no tienden a dejar este tipo de situaciones hasta la inferencia de tipos de todos modos.