understanding Haskell/GHCI behavior for recursion

Question

I'm trying to make sense of what I'm seeing with the following function. Not sure if my understanding is incorrect or if this is the behavior specific to the GHC implementation of 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

I'm seeing something that I'm not able to explain with this code.

*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)

For example :tracing through the below run with GHCI, I see that when we reach the singleton list with an element that has NOT been repeated yet, we do NOT recurse back each step.

*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> 

I was expecting that the last :step would take me back to the else y case in the definition, but instead I see that the result is returned immediately. But when the last char was present before then we recurse back and do the (fst y, (snd y) + 1) part... Can someone please tell what is happening? is my understanding incorrect or is GHCI optimizing something. If it is optimizing, how does it know it has to return the result directly? Any reference to this would be of great help.

Answer 1

The recursion you're expecting (namely, the evaluation of else y) is a procedural expectation that isn't needed in Haskell's lazy evaluation.

• y has already been evaluated in the where y = countNumLastChar xs statement when it was needed to evaluate the if, so it doesn't need to be evaluated again. (else y isn't showing up in the trace, because there's nothing new to evaluate)
• then (fst y, (snd y) + 1) has not been evaluated when the function reaches the singleton case, so you do see it evaluated on the way back up the recursive stack.

If you were to change the else case to something that couldn't be evaluated until after the singleton case, it would be evaluated on the way back up the recursive calls.