Perché alcune funzioni Data.List.Split utilizzano `Int` e altri` Integral a`?

Question

Qui ci sono le firme di tipo chunksOf e splitPlaces da Data.List.Split:

chunksOf :: Int -> [e] -> [[e]] 
splitPlaces :: Integral a => [a] -> [e] -> [[e]] 

Perché alcune funzioni (come chunksOf) utilizzare Int, mentre altri (come splitPlaces) utilizzano il più generico Integral a?

Answer 1

In questa risposta, provo a esaminare i motivi storici dell'interfaccia incoerente. Sommario: Sembra che Brent abbia reso alcune funzioni più generiche al volo per aiutare a formulare le proprietà di QuickCheck.

Perché è splitPlaces generico?

Sembra che Brent abbia generalizzato il tipo di splitPlaces per semplificare l'introduzione delle proprietà QuickCheck per tale funzione. Le proprietà QuickCheck utilizzano wrapper newtype per controllare la generazione del caso di test e, con il vincolo Integral a, splitPlaces è possibile esaminare questo wrapper newtype per le operazioni aritmetiche. Vedi anche:

• The patch che generalizza il tipo di splitPlaces e introduce le proprietà QuickCheck.

• The QuickCheck documentation su questi involucri newtype.

Tuttavia, qui è una delle proprietà su splitPlaces:

prop_splitPlaces_preserve :: [NonNegative Integer] -> [Elt] -> Bool 
prop_splitPlaces_preserve ps l = concat (splitPlaces ps' l) == genericTake (sum ps') l 
    where ps' = map unNN ps 

Nota che QuickCheck genera automaticamente la lista ps che viene convertito da map unNN ps prima di essere passato a splitPlaces. La funzione unNN rimuove il wrapper NonNegative, quindi splitPlaces non ha a che fare con il wrapper NonNegative. Tuttavia, riceve un argomento di tipo [Integer] anziché [Int], quindi deve ancora essere generico nel tipo numerico.

Qual è lo scopo di utilizzare [NonNegative Integer] anziché [NonNegative Int]?

Ho il sospetto che la proprietà sia falsa per [Int] a causa degli overflow aritmetici durante il calcolo della somma. La proprietà potrebbe anche essere falsificabile tramite QuickCheck perché l'istanza alla fine delegherà a arbitrarySizedBoundedIntegral che può generare valori molto grandi.

immagino che l'utilizzo di [NonNegative Integer] aggira invece questo problema in due modi:

1. Con Integer, non possono verificarsi overflow.
2. L'istanza Arbitrary Integer invia delegati a arbitrarySizedIntegral che genera solo valori piccoli.

quindi credo che la ragione per consentire tipi interi arbitrari è che la proprietà QuickCheck fallirebbe per Int ma riesce per Integer.

Perché chunksOf non è generico?

Le proprietà per chunksOf utilizzano la corrispondenza del modello per rimuovere i wrapper newtype. Vedi anche:

• The patch che introduce le proprietà per splitEvery.

• The patch che rinomina splitEvery a chunksOf.

Ecco una delle proprietà su chunksOf:

prop_chunksOf_all_n :: Positive Int -> NonEmptyList Elt -> Bool 
prop_chunksOf_all_n (Positive n) (NonEmpty l) = all ((==n) . length) (init $ chunksOf n l) 

notare che la struttura soddisfa sugli argomenti che vengono generati automaticamente da QuickCheck e li passa al chunksOf senza l'involucro newtype. Per gli argomenti necessari per il test chunksOf, questo è facile da fare, perché i numeri non sono nidificati in altri tipi. Confronta con prop_splitPlaces_preserve sopra, dove la conversione da [NonNegative Integer] a [Integer] o [Int] richiede qualcosa di più complicato della semplice corrispondenza del modello.

La differenza tra Arbitrary Int e Arbitrary Integer non importa qui, poiché la proprietà non comporta operazioni che possono attivare un overflow aritmetico.