7

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.

Improve this question
6
  • not able to edit the Q, hence the continuation here. IFF GHCI is optimizing this, is it considered a tail call optimization? But without doing the comparison, between x and fst y how is GHCI even making a call to optimize is what is puzzling me... Commented Aug 24, 2015 at 13:41
  • Optimizations should never lead to different answers from pure code. In very rare cases (when your code does something ill-advised) they can cause exceptions that technically shouldn't happen. That's not the case here. What do you expect your program to do? Commented Aug 24, 2015 at 13:50
  • @ dfeuer: I think the program is doing what it is expected to do. this is trying to count the number of occurrences of the last "char"/ element in that list... I'm trying to see if there is an optimization going on here. If so what is that technique called and other info on that. Commented Aug 24, 2015 at 14:30
  • I don't have a definitive answer but I suspect this happens because of a combination of sharing, a conversion to continuation passing style and perhaps even tail-call elimination? I tried to write up a quick explanation but I feel like I don't have a good enough grasp of what really happens to be able to do that. Commented Aug 24, 2015 at 15:01
  • 1
    It looks like you are not getting to else y simply because nothing there needs to be evaluated. y is already evaluated and else is not an expression. Commented Aug 28, 2015 at 5:52

1 Answer 1

Reset to default
2

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Haskell doesn't have stack frames in the same vein as a procedural language. Think of Haskell's stack resembling a mathematical equation, where each recursive call is a term in the equation. In the case where the last letter is not repeated, the equation is "solved" once the singleton case is hit. Then, just like in math, there's no reason to restate any of the original "terms", because the solution has been found. (i.e. in f('abc')=f('bc')=f('c')=('c',1) all terms are equal to ('c',1) without any more work to be done)
But it's running on a von Neumann machine, so it must use stack frames! I understand your very high-level explanation, but I'm interested in what actually happens in the registers and memory.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.