Why does MC Haskell function result in stack overflow

Question

I am working my way through the Haskell book and am on chapter 8. While doing the exercises I noticed something I didn't understand.

Why does this result in stack overflow

mc x | x>100 = x-10
     | otherwise = mc $ mc x+11

but this doesn't

mc x | x>100 = x-10
     | otherwise = mc $ mc (x+11)

I think it has something to do with x+11 not being evaluated in the first example but aren't expressions like that always evaluated

for example

Prelude> id 43+94
137

Hint: id (43 + 94) == (id 43) + 94, but that's not true for an arbitrary function. — chepner
– chepner, Commented Sep 18, 2019 at 21:03

willeM_ Van Onsem · Accepted Answer · 2019-09-18 20:59:23Z

6

The first expression

mc $ mc x+11

is interpreted as

mc ((mc x) + 11)

since function application takes precedence over operators.

The second expression

mc $ mc (x+11)

is interpreted as:

mc (mc (x+11))

The first indeed will never get evaluated, since if you write:

mc x | x > 100 = x-10
     | otherwise = mc ((mc x) + 11)

then you define mc x in terms of mc x. Unless that mc x in that expression is not evaluated, you thus will call mc x, when calculating mc x, and thus it will keep making calls.

answered Sep 18, 2019 at 20:59

willeM_ Van Onsem

482k33 gold badges483 silver badges624 bronze badges

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

Comments

Robin Zigmond · Accepted Answer · 2019-09-18 20:59:33Z

4

It's purely about operator precedence. In particular, function application takes precedence over all operators. So this:

mc x+11

is actually parsed as

(mc x)+11

and the fact that you tried to "visually" indicate the desired grouping by spacing or lack of it makes no difference. This of course is why your second version works better, since you explicitly indicated the grouping you want.

Of course, the unintended interpretation means that, for x <= 100, in order to evaluate mc x the compiler has to first evaluate mc x, and so on ad infinitum. Hence the eventual stack overflow.

answered Sep 18, 2019 at 20:59

Robin Zigmond

18.3k2 gold badges25 silver badges38 bronze badges

Collectives™ on Stack Overflow

Why does MC Haskell function result in stack overflow

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related