C'è una buona ragione per cui `deleteBy` non ha il suo tipo più generale?

Question

Haskell 2010 Lingua Denuncia stati nella sezione 20.10.1.1 che:

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

Infatti, l'attuazione nel GHC library permetterebbe

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

ma in realtà limita il tipo da quello precedente con la annotazione.

Quindi, non si può dire, per esempio:

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

perché Int non è la stessa come (Int, String).

C'è qualche buona ragione per questo?

La ragione per cui sto chiedendo è che, se non c'è una buona ragione, includo deleteBy con il tipo più generale nella porta Frege di Data.List che sto facendo attualmente. Ma forse sto trascurando qualcosa?

MODIFICA: come ha sottolineato @hammar, questo vale per altri xxx Per funzioni anche.

Answer 1

Generalizzare il tipo di deleteBy viola lo standard in un modo molto pratico: programmi Haskell perfettamente validi non sono più validi, grazie al sovraccarico irrisolto.

Ecco una dimostrazione:

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] 

In Haskell, questo programma è perfettamente digitato-; Il tipo limitato deleteBy garantisce che lo 42 abbia lo stesso tipo dello 1234. Con il numero deleteBy generalizzato, questo non è il caso, quindi il tipo di 42 è ambiguo, rendendo il programma non valido. (Se volete un esempio meno artificioso, si consideri una funzione che confronta due Integral valori con toInteger.)

Così, forse non v'è alcuna buona ragione per questo tipo limitato (anche se deleteBy deve essere generalizzato, preferirei Hammar di versione alla proposta), ma la sua generalizzazione è viola lo standard e può interrompere i programmi validi.

Answer 2

Immagino che sia per simmetria con le altre funzioni xxxBy. Tuttavia, il tuo tipo è ancora inutilmente specifico. Preferirei questo.

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

È quindi possibile scrivere il vostro esempio utilizzando l'applicazione parziale:

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

Answer 3

Ingo,

nella tua domanda iniziale, sembra che stai chiedendo perché Haskell relazione specifica deleteBy come questo . Quindi, se non c'è una ragione valida, è possibile utilizzare una definizione diversa in Frege (sottintendendo che non ti interessa la conformità al rapporto Haskell).

Come dice Hammar, è come le altre funzioni xxxBy: eliminare utilizza (==), deleteBy prende un predicato che è come (==): di tipo (A -> a - > Bool) e si presume che sia una relazione di equivalenza. Mentre il sistema di tipi non può controllare se il predicato è in realtà una relazione di equivalenza, è il contratto di funzione. Quindi è molto facile capire cosa significa xxxBy se sai cosa significa xxx. E forse non è il caso di deleteBy, ma in alcuni casi un'implementazione potrebbe essere ottimizzata assumendo che il predicato abbia le proprietà specificate (relazione di equivalenza o ordine totale, ecc.).

Ma nel tuo commento alla risposta di Hammar, chiedi se l'implementazione più generale violerebbe il rapporto. Bene, se il tipo è diverso allora è letteralmente una violazione, giusto? Poiché i programmi che non dovrebbero essere compilati in base al rapporto verranno accettati dal compilatore. In questo modo si genera un problema di portabilità: se il codice utilizza la versione più generale, potrebbe non essere compilato su un'altra implementazione conforme alle specifiche. Inoltre, elimina il requisito della relazione di equivalenza.

Quindi, se si desidera una funzione più generale, perché non definire semplicemente un'altra funzione con un nome diverso? Ad esempio, deleteIf.

(volevo commentare la risposta di Hammar, ma non posso quindi ho scritto qui.)