Eficiencia de igualdad en Haskell

Question

Tengo una función que toma datos y devuelve los mismos datos o una versión ligeramente modificada.

Quiero que mi programa haga una cosa si cambia o algo más si no cambia.

Anteriormente devolvía un par (Bool,Object) y usaba fst para comprobar si cambiaba. Últimamente se me ocurrió que podía simplificar el código simplemente devolviendo el objeto y comprobando la igualdad usando ==.

Pero luego me di cuenta de que Haskell no diferencia entre comprobación profunda de igualdad e "identidad de objeto" (es decir, igualdad de puntero). Entonces, ¿cómo puedo saber si usar == va a ser eficiente o no? ¿Debería evitarlo por razones de eficiencia, o hay casos en los que puedo depender de que el compilador se dé cuenta de que no necesita hacer una profunda verificación de igualdad?

Normalmente no estaría demasiado preocupado por la eficiencia mientras escribo un programa inicial, pero esto afecta la interfaz de mi módulo, así que quiero hacerlo bien antes de escribir demasiados códigos, y no parece que valga la pena haga que el programa sea mucho menos eficiente solo para una pequeña porción de código. Además, me gustaría tener una mejor idea de qué tipo de optimizaciones puedo depender de GHC para que me ayuden.

Answer 1

Siempre es una mala idea confiar en las optimizaciones inciertas del compilador para proporcionar una garantía de rendimiento tan importante como la igualdad en tiempo constante frente a la igualdad profunda en tiempo lineal. Está mucho mejor con un nuevo tipo que encapsula un valor más información sobre si el valor es nuevo. Dependiendo de su aplicación, este puede ser

data Changed a = Changed a | Unchanged a 

o

data Changed a = Changed a | Unchanged 

Utilizamos realmente un tipo similar dentro de la Haskell Compiler Glasgow para que podamos seguir ejecutando el optimizador hasta que el código deja de cambiar. También ejecutamos análisis iterativos de flujo de datos hasta que los resultados dejan de cambiar.

Nos pareció útil hacer de este tipo una mónada para que podamos escribir algunas funciones simples de orden superior utilizando la notación do, pero no es necesario — simplemente para su conveniencia.

Resumen: Si desea constante en tiempo de comprobación, el código usted mismo — no se basan en una posible optimización del compilador que podría no estar allí — o podria cambiar en la próxima versión.

Answer 2

Sigo siendo un novato haskell relativo, así que toma mi respuesta con mucho mimo, y por favor perdóname si mi respuesta no es tan directa como debería ser.

En Haskell, los operadores no son especiales, solo son funciones infrecuentes.

Puede ver el definition of the equality operator usted mismo en el preludio estándar.

Por supuesto, se puede sobrecargar para trabajar con cualquier tipo de datos que haya definido, pero si se sobrecarga, sabrá cuán eficiente es la implementación.

Puede ser útil saber que puede usar Hoogle para encontrar la definición de la función que desea. Así es como encontré la definición del operador de igualdad.

Answer 3

El derivado (==) siempre es una comparación profunda. Tu pregunta ha sido discussed en haskell-cafe.