Haskell - overflow stack C

Question

Sono appena stato presentato a Haskell, quindi non sono molto pratico su come codificare nella lingua, e quindi, scusa se questo è un duplicato, tuttavia non capisco l'altro codice scritto nella lingua

Sto provando a scrivere un algoritmo che prenderà la somma degli interi pari positivi non superiore al valore indicato. Ho tentato di scrivere il codice, tuttavia ho ricevuto l'errore di overflow dello stack C.

Ecco il mio codice:

sumint :: Int -> Int 
sumint x 
    | x==0 = 0 
    | x==1 = 1 
    | (x `mod` 2 == 0) && (x >= 2) = x + (sumint x-2) 
    | (x `mod` 2 /= 0) && (x >= 1) = x + (sumint x-1) 

Dove sto andando male per ottenere questo errore?

Answer 1

errore iniziale: Ricorsione infinita

Stepping attraverso il codice:

sumint :: Int -> Int 

Ehi, un tipo di firma. Sei forte.

sumint x 
    | x==0 = 0 

Un caso base, fresco.

| x==1 = 1 

Un caso totalmente inutile. OK, certo ... tranne. 1 non è nemmeno così perché lo includiamo nella somma? Dovrebbe essere zero (o rimosso completamente).

| (x `mod` 2 == 0) && (x >= 2) = x + (sumint x-2) 

La carne del problema è qui. 1. X è pari, ottimo. 2. X è positivo, sì. Il risultato è x + (sumint x) - 2 No!

• Errore 1: l'applicazione della funzione di avviso si associa più agli operatori, pertanto dovrebbe essere x + sumint (x-2).

Questo è il motivo per il sovraccarico dello stack. sumint 2 == 2 + (sumint 2) - 2 + (sumint 2) -2 + (sumint 2) -2 + ..., yay ricorsione infinita.

| (x `mod` 2 /= 0) && (x >= 1) = x + (sumint x-1) 

Un altro caso ... quote ... positivo ... ma perché stiamo aggiungendo in x? Vuoi aggiungere uniformi, non quote. Quindi fissare il problema di cui sopra, allo stesso tempo otteniamo:

• Errore 2: Se si determina x è dispari, non aggiungere in x. Basta usare sumint (x-1).

Quindi sei fuori dai casi. Cosa succede se x non è positivo? Hai bisogno di (altro) caso.

| otherwise = 0 

prossimo numero: No Capitalizzazione

Il problema ora è che si sta costruendo una grande thunk (calcolo non valutata) invece di operare nello spazio costante accumulando il risultato, come si procede. Notate se espandiamo il vostro calcolo per, diciamo, 6 otteniamo:

sumint 6 = 6 + sumint (6-2) 
     = 6 + 4 + sumint (4-2) 
     = 6 + 4 + 2 + sumint (2-2) 
     = 6 + 4 + 2 + 0 

davvero non si desidera mantenere tutte quelle aggiunte separano, sarebbe bene passare in un accumulatore come ad esempio:

sumint x = go x 0 
where 
    go n accumulator 
     | n <= 0 = accumulator 
     | odd n  = go (n-1) accumulator 
     | otherwise = go (n-2) (accumulator + n) 

Nota a margine: altri cittadini stackoverflow potrebbero menzionare la necessità di rendere l'accumulatore rigido, che è una buona forma. Non voglio distrarre l'attuale richiedente con quella discussione qui. Si noti che l'utilizzo dell'ottimizzazione, -O2, è sufficiente.

Solutions idiomatiche

Tutte le soluzioni di cui sopra sono piuttosto prolisso. L'operazione generale, che scorre su un elenco con una funzione e un accumulatore, è un tipo di fold. I fold sono uno dei tanti traversamenti della struttura altamente ottimizzati comuni nella programmazione funzionale. In questo caso una "piega a sinistra rigorosa" è il tipico candidato (da Data.List). Questo è foldl' 'il primo (') per convenzione significa che è rigoroso mentre il l significa sinistra.

sumint n = foldl' (+) 0 [val | val <- [0..n], even val] 

Qui abbiamo passato la lista per ottenere la nostra somma. Per creare l'elenco di interesse, abbiamo utilizzato la comprensione delle liste, innanzitutto elencando i valori da 0..n e ignorando qualsiasi valore che non soddisfa il predicato even.

Possiamo ulteriormente pulire questo e migliorarla utilizzando la funzione e la lista sum di comprensione che passi a 2, dandoci così solo le dispari che desiderate:

sumint n = sum [0,2..n] 

Answer 2

È un problema di precedenza di operatore. In Haskell, l'applicazione di funzione ha la precedenza più alta possibile. Pertanto, quando scrivi sumint x - 2, anche se lo stai interpretando come sumint (x-2), Haskell lo sta interpretando come (sumint x) - 2. Quindi, stai provando a definire sumint x direttamente in termini di sumint x - che accumula solo chiamate di funzioni ricorsive fino a quando lo stack non viene espulso. È necessario aggiungere parentesi esplicite se si desidera che la sottrazione venga valutata prima dell'applicazione della funzione.