Portando il tipo di funzione dipendono ingresso

Question

Quindi notato che dopo n = 20 la funzione fattoriale data a LearnYouAHaskell (sotto) craps fuori a causa della gamma lavoro finito di tipo Int.

factorial :: Int -> Int 
factorial 0 = 1 
factorial n * factorial (n-1) 

Utilizzando factorial :: Integer -> Integer risolve il problema bene, ma ha portato alla mente la questione. Presumibilmente Integer è leggermente più lento Int così idealmente (e so che sto intrappolando i penny qui) vorrei la mia funzione fattoriale di ricorrere solo per intero quando l'ingresso è maggiore di 20 e mantenere il tipo di Int->Int per i numeri più piccoli. Sembra che ci dovrebbe essere una soluzione elegante per questo utilizzando if-then-else o guards, ma continuare a correre in pepe sintattico (messaggi di errore)

Answer 1

È possibile effettuare una soluzione di hacker senza tipi dipendenti utilizzando sia un tipo di somma e crescente in caso di necessità o ritardare il cast al Integer fino alla fine, in alcuni casi. Non mi aspetto che entrambe le soluzioni funzionino meglio di Integer - non temete che Integer, gmp e mpir siano abbastanza buoni.

La soluzione di colata è qualcosa di simile:

selectiveFactorial :: Integer -> Integer 
selectiveFactorial i 
    | i < 20 = fromIntegral $ factorial (fromIntegral i :: Int) 
    | otherwise = factorial i 

factorial :: Integral a => a -> a 
factorial 0 = 1 
factorial n = n * factorial (n - 1) 

Answer 2

Fare in modo che il tipo di una funzione dipenda dai suoi valori è esattamente ciò per cui sono dependent types. Sfortunatamente, Haskell non ha tipi dipendenti, quindi non può essere fatto.

Answer 3

Esso non può essere fatto. Ci sono cose che puoi fare comunque:

1. Rendere il tipo più generico: factorial :: Num a => a -> a; Questo consente all'utente della funzione di decidere quali sanzioni runtime che vuole a verificarsi rispetto a quello che intervallo di numeri è ammissibile.

2. Utilizzare un tipo di somma come data PossiblyBig = Small Int | Big Integer, e quindi avere un'implementazione instance Num PossiblyBig che codifica per le cose che si inseriscono nel Int come Small, e le cose che non si adattano come Big; Per quanto ne so Integer funziona già così (guarda l'attuazione GMP se volete sapere di sicuro), quindi questo è più di un esempio generale di consigli su cosa si dovrebbe fare in questa particolare situazione.

Answer 4

Come Rein Henrichs said si potrebbe fare queste cose in una lingua con tipi dipendenti, che Haskell non lo fa (ancora, del tutto) avere. In Idris, per esempio, sarebbe simile a

factorial : (n : Int) -> if n <= 20 then Int else Integer 
factorial n with (n <= 20) 
    factorial n | True = thisfactorial n 
    factorial n | False = thatfactorial n 

Ma come si utilizzare questo risultato? Bene, dovrai fare il confronto per capire che tipo aspettarti, e quando tutto è detto e fatto, non vedo come hai vinto nulla. Per completezza, il sito di utilizzo può sembrare qualcosa di simile:

use : Int -> Integer 
use n with (factorial n) 
    use n | fn with (n <= 20) 
    use n | fn | False = fn 
    use n | fn | True = cast fn 

Si noti che l'ordine delle clausole with è significativo! Il binding fn ottiene il tipo if n <= 20 then Int else Integer; per motivi che non capisco del tutto, il test n <= 20 deve essere a destra di quello in modo che la corrispondenza del modello influenzi il suo tipo.