Search code examples
haskellrecursionfixpoint-combinators

How McCarthy 91 function works

I have following function based on McCarthy 91 principle:

mc91 :: Integer -> Integer
mc91 n
    | n > 100 = n - 10
    | otherwise = mc91 (mc91 (n + 11))

when I type in the prelude mc91 85 I've got 91.

I could not configure it out, how it is expanded and why do I've got 91.

Solution

  • Lets expand your code:

    mc91 85
mc91 (mc91 96)
mc91 (mc91 (mc91 107))
mc91 (mc91 97)
mc91 (mc91 (mc91 108))
mc91 (mc91 98)
mc91 (mc91 (mc91 109))
mc91 (mc91 99)
mc91 (mc91 (mc91 110))
mc91 (mc91 100)
mc91 (mc91 (mc91 111))
mc91 (mc91 101)
mc91 91... --It is a pattern here
...
mc91 101
91

    If you see the recrusive calls, you will realize that it will reduce it once it achieves 100 or higher, ending in a (mc91 101) call that will bring us the last 91 result.