2012-01-25 17 views
18

Los Haskell 2010 señala el Informe de idiomas en la sección 20.10.1.1 que:¿Hay una buena razón por la cual `deleteBy` no tiene su tipo más general?

deleteBy :: (a -> a -> Bool) -> a -> [a] -> [a] 

De hecho, la aplicación en la GHC library permitiría

deleteBy :: (b -> a -> Bool) -> b -> [a] -> [a] 

pero en realidad restringe el tipo a la anterior con el anotación.

Por lo tanto, no se puede decir, por ejemplo:

foo = deleteBy fsteq 42 [(43, "foo"), (44, "bar"), (42, "baz")] where 
    fsteq a (b,_) = a == b 

porque Int no es lo mismo que (Int, String).

¿Hay alguna buena razón para esto?

La razón por la que estoy preguntando es que, si no hay una buena razón para ello, incluiría deleteBy con el tipo más general en el puerto Frege de Data.List que estoy haciendo actualmente. Pero tal vez estoy pasando por alto algo?

EDITAR: Como @hammar señaló, esto se aplica a otras xxx Por funciones también.

Respuesta

11

Generalizar el tipo de deleteBy viola la norma de una manera muy práctica: programas Haskell perfectamente válidas dejan de ser válidas, gracias a la sobrecarga no resuelta.

Aquí es una demostración:

class (Num a) => Magic a where 
    magic :: a -> Bool 

sameMagic :: (Magic a, Magic b) => a -> b -> Bool 
sameMagic a b = magic a == magic b 

test :: (Magic a) => [a] 
test = deleteBy sameMagic 42 [1234] 

En Haskell, este programa es perfectamente bien escrito; El tipo restringido de deleteBy garantiza que se garantice que el 42 tenga el mismo tipo que el 1234. Con el deleteBy generalizado, este no es el caso, por lo que el tipo de 42 es ambiguo, por lo que el programa no es válido. (Si quieres un ejemplo menos artificiosa, considere una función que compara dos Integral valores con toInteger.)

Por lo tanto, tal vez no hay una buena razón para este tipo restringido (aunque si deleteBy es generalizar, yo preferiría hammar de versión a su propuesta), pero al generalizarlo hace violar el estándar, y puede romper programas válidos.

+1

Ese es el tipo de comentarios perspicaces que estaba buscando. Me da algo en qué pensar. – Ingo

+0

¡Esta es una respuesta muy perspicaz! – danr

+0

¿Pero no debería resolverse 42 en 'Entero' por reglas de tipo de incumplimiento? – haskelline

10

Supongo que es por simetría con las otras funciones xxxBy. Sin embargo, tu tipo sigue siendo innecesariamente específico. Yo preferiría esto

deleteBy :: (a -> Bool) -> [a] -> [a] 

A continuación, podría escribir su ejemplo usando una aplicación parcial:

foo = deleteBy (fsteq 42) [(43, "foo"), (44, "bar"), (42, "baz")] where 
    fsteq a (b,_) = a == b 
+0

Excepto que el filtro eliminaría * todos * elementos iguales, donde deleteBy debe eliminar solo el primero. – Ingo

+0

@Ingo: ¡Vaya! Estás absolutamente en lo correcto. 'filter' no hará el trabajo aquí. – hammar

+1

Claro, hay formas de evitarlo, pero como ve, el objetivo es mantener el estándar (Haskell 2010, en este caso). La pregunta es si viola el estándar si uno es un poco más general. – Ingo

7

Ingo,

en su pregunta original, parece que estás preguntando por qué Haskell informe especifica deleteBy como esto . Por lo tanto, si no existe una razón sólida, podría utilizar una definición diferente en Frege (lo que implica que no le importa la conformidad con el informe Haskell).

Como dice Hammar, es como las otras funciones xxxBy: eliminar utiliza (==), deleteBy toma un predicado que es como (==): de tipo (a -> a - > Bool) y se supone que es una relación de equivalencia. Si bien el sistema de tipos no puede verificar si el predicado es realmente una relación de equivalencia, es el contrato de función. Entonces, es muy fácil entender lo que significa xxxBy si sabes lo que significa xxx. Y tal vez no sea el caso de deleteBy, pero en algunos casos una implementación podría optimizarse bajo la suposición de que el predicado tiene las propiedades especificadas (relación de equivalencia o orden total, etc.).

Pero en su comentario a la respuesta de Hammar, usted pregunta si la implementación más general violaría el informe. Bueno, si el tipo es diferente, es literalmente una violación, ¿verdad? Dado que los programas que no deberían compilarse de acuerdo con el informe serán aceptados por su compilador. Por lo tanto, da lugar a un problema de portabilidad: si su código usa la versión más general, es posible que no compile en otra implementación que cumpla con la especificación. Además, elimina el requisito de relación de equivalencia.

Entonces, si quiere una función más general, ¿por qué no simplemente define otra función con un nombre diferente? Por ejemplo, deleteIf.

(quería hacer comentarios sobre la respuesta de Hammar, pero no puedo por lo que escribió aquí.)

+0

Rafael, bueno, usted escribió esto como respuesta, entonces pude +1. – Ingo

Cuestiones relacionadas