I tipi Haskell frustrano una semplice funzione "media"

Question

Sto giocando con il principiante Haskell e volevo scrivere una funzione media. Sembrava la cosa più semplice del mondo, giusto?

Errore.

Sembra che il sistema di tipi di Haskell impedisca al media di lavorare su un tipo numerico generico - Posso farlo funzionare su un elenco di Integrali, o su un elenco di Frazionali, ma non su entrambi.

voglio:

average :: (Num a, Fractional b) => [a] -> b 
average xs = ... 

ma posso ottenere solo:

averageInt :: (Integral a, Fractional b) => [a] -> b 
averageInt xs = fromIntegral (sum xs)/fromIntegral (length xs) 

o

averageFrac :: (Fractional a) => [a] -> a 
averageFrac xs = sum xs/fromIntegral (length xs) 

e il secondo sembra funzionare. Fino a quando non provo a passare una variabile.

*Main> averageFrac [1,2,3] 
2.0 
*Main> let x = [1,2,3] 
*Main> :t x 
x :: [Integer] 
*Main> averageFrac x 

<interactive>:1:0: 
    No instance for (Fractional Integer) 
     arising from a use of `averageFrac ' at <interactive>:1:0-8 
    Possible fix: add an instance declaration for (Fractional Integer) 
    In the expression: average x 
    In the definition of `it': it = averageFrac x 

A quanto pare, Haskell è davvero pignolo per i suoi tipi. Ciò ha senso. Ma non quando potrebbero essere entrambi [Num]

Mi manca un'applicazione evidente di RealFrac?

C'è un modo per forzare gli Integrali in Frazionali che non soffocano quando riceve un input Frazionario?

C'è un modo per utilizzare Either e either per creare una sorta di funzione media polimorfa che possa funzionare su qualsiasi tipo di matrice numerica?

Il sistema di tipo Haskell a titolo definitivo vieta questa funzione da sempre esistente?

L'apprendimento di Haskell è come imparare il calcolo. È davvero complicato e basato su montagne di teoria e, a volte, il problema è così complesso che non conosco abbastanza bene per formulare correttamente la domanda, quindi qualsiasi intuizione sarà caldamente accettata.

(Inoltre, nota a piè di pagina: questo è basato su un problema di compiti a casa. Tutti concordano sul fatto che MediaFrac, sopra, ottiene punti pieni, ma ho un vago sospetto che esiste un modo per farlo funzionare su entrambi gli array Integral AND Fractional)

Answer 1

Quindi fondamentalmente, il gioco è vincolata dal tipo di (/):

(/) :: (Fractional a) => a -> a -> a 

BTW, anche voi volete Data.List.genericLength

genericLength :: (Num i) => [b] -> i 

Così

come circa la rimozione del fromIntegral per qualcosa di più generale:

import Data.List 

average xs = realToFrac (sum xs)/genericLength xs 

che ha solo un vincolo reale (Int, integer, float, double) ...

average :: (Real a, Fractional b) => [a] -> b 

In modo che prenderò qualsiasi reale in qualsiasi frazionale

E si noti che tutti i poster vengono catturati dai letterali numerici polimorfici in Haskell. 1 non è un numero intero, è un numero qualsiasi.

La classe Real fornisce un solo metodo: la possibilità di trasformare un valore in codice Num in un razionale. Che è esattamente ciò di cui abbiamo bisogno qui.

E così,

Prelude> average ([1 .. 10] :: [Double]) 
5.5 
Prelude> average ([1 .. 10] :: [Int]) 
5.5 
Prelude> average ([1 .. 10] :: [Float]) 
5.5 
Prelude> average ([1 .. 10] :: [Data.Word.Word8]) 
5.5 

Answer 2

Sì, digitare sistema di Haskell è molto esigente. Il problema qui è il tipo di fromIntegral:

Prelude> :t fromIntegral 
fromIntegral :: (Integral a, Num b) => a -> b 

fromIntegral sarà solo accettare un integrale come, senza alcun altro tipo di Num. (/), d'altra parte accetta solo frazionale. Come si fa a lavorare insieme?

Beh, la funzione somma è un buon inizio:

Prelude> :t sum 
sum :: (Num a) => [a] -> a 

Somma prende una lista di qualsiasi Num e restituisce un Num.

Il tuo prossimo problema è la lunghezza della lista. La lunghezza è un Int:

Prelude> :t length 
length :: [a] -> Int 

È necessario convertire anche Int in Num. Questo è ciò che fa Integrale.

Quindi ora hai una funzione che restituisce un Num e un'altra funzione che restituisce un Num. Ci sono alcune regole per tipo di promozione dei numeri you can look up, ma in fondo a questo punto siete pronti per partire:

Prelude> let average xs = (sum xs)/(fromIntegral (length xs)) 
Prelude> :t average 
average :: (Fractional a) => [a] -> a 

Diamo un giro di prova:

Prelude> average [1,2,3,4,5] 
3.0 
Prelude> average [1.2,3.4,5.6,7.8,9.0] 
5.4 
Prelude> average [1.2,3,4.5,6,7.8,9] 
5.25 

Answer 3

La domanda è stata molto bene rispose Dons, pensavo di poter aggiungere qualcosa.

Nel calcolare la media in questo modo:

average xs = realToFrac (sum xs)/genericLength xs

Che il codice farà è quello di attraversare l'elenco due volte, una volta per calcolare la somma dei suoi elementi, e una volta per ottenere la sua lunghezza. Per quanto ne so, GHC non è ancora in grado di ottimizzare questo e calcolare sia la somma che la lunghezza in un singolo passaggio.

Non fa male nemmeno come un principiante a pensarci e sulle possibili soluzioni, ad esempio la funzione media potrebbe essere scritta utilizzando una piega che calcola sia la somma che la lunghezza; on ghci:

:set -XBangPatterns 

import Data.List 

let avg l=let (t,n) = foldl' (\(!b,!c) a -> (a+b,c+1)) (0,0) l in realToFrac(t)/realToFrac(n) 

avg ([1,2,3,4]::[Int]) 
2.5 
avg ([1,2,3,4]::[Double]) 
2.5 

La funzione non sembra elegante, ma le prestazioni sono migliori.

Maggiori informazioni sul blog Dons:

http://donsbot.wordpress.com/2008/06/04/haskell-as-fast-as-c-working-at-a-high-altitude-for-low-level-performance/

Answer 4

Dal Dons ha fatto un buon lavoro a rispondere alla tua domanda, io lavoro su in discussione la vostra domanda ....

Per esempio , nella tua domanda, in cui per la prima volta esegui una media su una determinata lista, ottieni una buona risposta. Quindi, si prende quello che sembra esattamente lo stesso elenco, assegnarlo a una variabile, quindi utilizzare la funzione la variabile ... che quindi esplode.

Cosa hai incontrato qui è un set-up nel compilatore, chiamato DMR: la D readed M onomorphic R estriction. Quando hai passato l'elenco direttamente nella funzione, il compilatore non ha fatto alcuna supposizione sul tipo di numeri, ha solo dedotto i tipi che potrebbero essere basati sull'utilizzo e ne ha selezionato uno una volta che non poteva più restringere il campo. È un po 'come l'esatto opposto del battere a macchina, lì.

Ad ogni modo, quando hai assegnato l'elenco a una variabile, il DMR ha dato il via. Dato che hai inserito l'elenco in una variabile, ma non hai dato alcun suggerimento su come vuoi usarlo, il DMR ha fatto scegliere al compilatore un digitare, in questo caso, ne ha selezionato uno che corrisponde al modulo e sembra adattarsi: Integer. Dal momento che la tua funzione non può utilizzare un numero intero nella sua operazione / (ha bisogno di un tipo nella classe Fractional), fa proprio questo reclamo: non c'è istanza di Integer nella classe Fractional. Ci sono opzioni che puoi impostare in GHC in modo da non forzare i tuoi valori in un unico modulo ("monomorfico", capito?) Finché non è necessario, ma rende leggermente più difficile l'individuazione dei messaggi di errore.

Ora, in un'altra nota, si aveva una risposta alla risposta dons' che ha attirato la mia attenzione:

sono stato indotto in errore dall'impiego tabella sull'ultima pagina di cs.ut.ee/~varmo/MFP2004 /PreludeTour.pdf che mostra la proprietà NON ereditante di Floating da Real e quindi ho assunto che non condividessero alcun tipo in comune.

Haskell esegue i tipi in modo diverso da quello a cui sei abituato. Real e Floating sono classi di tipi, che funzionano più come interfacce che classi di oggetti. Ti dicono cosa puoi fare con un tipo che è in quella classe, ma ciò non significa che alcuni tipi non possono fare altre cose, più che avere un'interfaccia significa che una classe (n OO-style) non può avere altri.

apprendimento Haskell è come imparare Calculus

direi imparando Haskell è come imparare svedese - ci sono un sacco di piccole, semplici cose (lettere, numeri), che appaiono e funzionano lo stesso, ma ci sono anche parole che sembrano voler dire una cosa, quando in realtà significano qualcos'altro. Ma una volta che ci sei riuscito, i tuoi amici abituali saranno stupiti di come puoi lanciare questa strana roba che fa fare bellezze meravigliose a trucchi incredibili. Curiosamente, ci sono molte persone coinvolte in Haskell dagli inizi, che conoscono anche lo svedese. Forse quella metafora è più di una semplice metafora ...

Answer 5

:m Data.List 
let list = [1..10] 
let average = div (sum list) (genericLength list) 
average