Understanding Haskell / GHCI Recursion Behavior

Question

I am trying to understand what I see with the following function. Not sure if my understanding is wrong or this is behavior specific to the GHC Haskell implementation.

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 see something that I cannot 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 in the next run using GHCI, I see that when we reach the list of single elements with an element that has NOT been repeated yet, we will NOT go back every 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 the latter :step will return me 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 that, we go back and do the part (fst y, (snd y) + 1) . Can anyone tell what is happening? my understanding is wrong or something optimizes GHCI. If he optimizes, how does he know that he should return the result directly? Any reference to this would be very helpful.

Answer 1

The recursion you expect (namely else y ) is a procedural expectation that is not required in a lazy Haskell evaluation.

• y has already been evaluated in the where y = countNumLastChar xs when it is necessary to evaluate if , so it does not need to be evaluated again. ( else y not displayed in the trace because there is nothing new to evaluate)
• then (fst y, (snd y) + 1) not evaluated when the function reaches the singleton case, so you see that it is evaluated by the backup path of the recursive stack.

If you changed the else case to something that could not be evaluated until after the singleton case, it would be evaluated along the backup path of the recursive calls.