comprensione comportamento Haskell/GHCI per la ricorsione

Question

Sto cercando di dare un senso a ciò che sto vedendo con la seguente funzione. Non sono sicuro se la mia comprensione non è corretta o se questo è il comportamento specifico dell'implementazione di GHC di Haskell.

countNumLastChar :: Eq a => [a] -> (a, Int) 
countNumLastChar [x]  = (x, 1) 
countNumLastChar (x:xs) = if x == fst y 
          then (fst y, (snd y) + 1) 
          else y 
          where y = countNumLastChar xs 

Sto vedendo qualcosa che non sono in grado di spiegare con questo codice.

*Main> countNumLastChar "aba" 
('a',2) 
*Main> countNumLastChar "abql;kejrqlwkjer;lqwkejr;lwjerca" 
('a',2) 
*Main> countNumLastChar "abql;kejrqlwkjer;lqwkejr;lwjercap" 
('p',1) 
*Main> countNumLastChar "abql;kejrqlwkjer;lqwkejr;lwjerca;" 
(';',4) 

Per esempio: analisi tramite la corsa sotto con GHCI, vedo che quando raggiungiamo la lista Singleton con un elemento che non è stato ancora ripetuto, noi NON Recurse indietro ogni passo.

*Main> countNumLastChar "aabc" 
('c',1) 
[maxOccurCharInStr.hs:(3,28)-(5,34)] *Main> :step 
Stopped at maxOccurCharInStr.hs:3:31-40 
_result :: Bool = _ 
x :: Char = 'b' 
y :: (Char, Int) = _ 
[maxOccurCharInStr.hs:3:31-40] *Main> :list 
2 countNumLastChar [x]  = (x, 1) 
3 countNumLastChar (x:xs) = if x == fst y 
4        then (fst y, (snd y) + 1) 
[maxOccurCharInStr.hs:3:31-40] *Main> :step 
Stopped at maxOccurCharInStr.hs:3:36-40 
_result :: a = _ 
y :: (a, Int) = _ 
[maxOccurCharInStr.hs:3:36-40] *Main> :step 
Stopped at maxOccurCharInStr.hs:6:39-57 
_result :: (Char, Int) = _ 
xs :: [Char] = 'c' : _ 
[maxOccurCharInStr.hs:6:39-57] *Main> :list 
5        else y 
6        where y = countNumLastChar xs 
7 
[maxOccurCharInStr.hs:6:39-57] *Main> :step 
Stopped at maxOccurCharInStr.hs:(2,1)-(6,57) 
_result :: (a, Int) = _ 
[maxOccurCharInStr.hs:(2,1)-(6,57)] *Main> :list 
1 countNumLastChar :: Eq a => [a] -> (a, Int) 
2 countNumLastChar [x]  = (x, 1) 
3 countNumLastChar (x:xs) = if x == fst y 
4        then (fst y, (snd y) + 1) 
5        else y 
6        where y = countNumLastChar xs 
7 
[maxOccurCharInStr.hs:(2,1)-(6,57)] *Main> :step 
Stopped at maxOccurCharInStr.hs:2:29-34 
_result :: (Char, Int) = _ 
x :: Char = 'c' 
[maxOccurCharInStr.hs:2:29-34] *Main> :list 
1 countNumLastChar :: Eq a => [a] -> (a, Int) 
2 countNumLastChar [x]  = (x, 1) 
3 countNumLastChar (x:xs) = if x == fst y 
[maxOccurCharInStr.hs:2:29-34] *Main> :step 
('c',1) 
*Main> 

mi aspettavo che l'ultima :step mi avrebbe riportato alla else y caso nella definizione, ma invece vedo che il risultato viene restituito immediatamente. Ma quando l'ultimo carattere era presente prima, ricambiamo e facciamo la parte (fst y, (snd y) + 1) ... Qualcuno può dirmi cosa sta succedendo? la mia comprensione è errata o GHCI sta ottimizzando qualcosa. Se si sta ottimizzando, come fa a sapere che deve restituire il risultato direttamente? Qualsiasi riferimento a questo sarebbe di grande aiuto.

Answer 1

La ricorsione che si sta aspettando (vale a dire la valutazione di else y) è un'aspettativa procedurale che non è necessaria nella valutazione lenta di Haskell.

• y è già stato valutato nella dichiarazione where y = countNumLastChar xs quando era necessario per valutare l'if, quindi non ha bisogno di essere valutato di nuovo. (else y non viene visualizzato nella traccia, perché non c'è nulla di nuovo da valutare)
• then (fst y, (snd y) + 1) non è stato valutato quando la funzione raggiunge il caso singleton, quindi è possibile vederlo valutato durante il backup dello stack ricorsivo.

Se si dovesse modificare il caso in caso contrario a qualcosa che non è stato possibile valutare fino a dopo il caso singleton, esso verrà valutato durante il backup delle chiamate ricorsive.