Mutable variables in Haskell?

Question

I'm starting to wrap my head around Haskell and do some exciting experiments. And there's one thing I just seem to be unable to comprehend (previous "imperativist" experience talks maybe). Recently, I was yearning to implement integer division function as if there where no multiply/divide operations. An immensely interesting brain-teaser which led to great confusion.

divide x y =
    if x < y then 0
    else 1 + divide (x - y) y

I compiled it and it.. works(!). That's mind-blowing. However, I was told, I was sure that variables are immutable in Haskell. How comes that with each recursive step variable x keeps it's value from previous step? Or is my glorious compiler lying to me? Why does it work at all?

This is no different than recursion in any other language. The value x - y you pass to the recursive call does not affect the value of x in the caller. — chepner
– chepner, Commented Oct 12, 2016 at 17:56
No, it's simply a different variable that also happens to be called x. This has nothing to do with mutability, like it has nothing to do with mutability if you define two functions f x = sin x and g x = tanh x. — leftaroundabout
– leftaroundabout, Commented Oct 12, 2016 at 18:03
Variables are called variables because they can assume various values -- they vary. In Haskell, they vary like in maths, where given f(x) we can refer to f(1), f(4), ... choosing x=1, and then x=4, .... This has nothing to do with mutability: within the same scope ("function call"), a variable in maths/Haskell has always the same value. In imperative language, assignment can alter such value. — chi
– chi, Commented Oct 12, 2016 at 18:29
@user2407038 Haskell doesn't just have parameters. You can also define local variables with let and where and of course you can also define them at the top-level. And of course parameters are just a kind of variable. — sepp2k
– sepp2k, Commented Oct 12, 2016 at 21:14

Tomasz Lewowski · Accepted Answer · 2016-10-12 20:28:00Z

5

Your x here doesn't change during one function call (i.e., after creation) - that's exactly what immutable means. What does change is value of x during multiple (recursive) calls. In a single stack frame (function call) the value of x is constant.

An example of execution of your code, for a simple case

call divide 8 3 -- (x = 8, y = 3), stack: divide 8 3
step 1: x < y ? NO
step 2: 1 + divide 5 3 
    call: divide 5 3 -- (x = 5, y = 3), stack: divide 8 3, divide 5 3
    step 1: x < y ? NO
    step 2: 1 + divide 2 3
        call divide 2 3 -- (x = 2, y = 3), stack: divide 8 3, divide 5 3, divide 2 3
        step 1: x < y ? YES
        return: 0 -- unwinding bottom call
    return 1 + 0 -- stack: divide 8 3, divide 5 3, unwinding middle call
return 1 + 1 + 0 -- stack: divide 8 3

I am aware that the above notation is not anyhow formalized, but I hope it helps to understand what recursion is about and that x might have different values in different calls, because it's simply a different instance of whole call, thus also different instance of x.

answered Oct 12, 2016 at 20:28

Tomasz Lewowski

1,97522 silver badges29 bronze badges

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

1 Comment

beatsbury Over a year ago

Yes, that definately was imperative programmer in me talking. I was looking at my code and seeing nothing behind that x. Thank you for the answer.

lvsz · Accepted Answer · 2016-10-13 03:54:37Z

x is actually not a variable, but a parameter, and isn't that different from parameters in imperative languages.

Maybe it'd look more obvious with explicit return statements?

-- for illustrative purposes only, doesn't actually work
divide x y =
    if x < y
    then return 0
    else return 1 + divide (x - y) y

You're not mutating x, just stacking up several function calls to calculate your desired result with the values they return.

Here's the same function in Python:

def divide(x, y):
    if x < y:
        return 0
    else:
        return 1 + divide(x - y, y)

Looks familiar, right? You can translate this to any language that allows recursion, and none of them would require you to mutate a variable.

Other than that, yes, your compiler is lying to you. Because you're not allowed to directly mutate values, the compiler can make a lot of extra assumptions based on your code, which helps translating it to efficient machine code, and at that level, there's no escaping mutability. The major benefit is that compilers are way less likely to introduce mutability-related bugs than us mortals.

Collectives™ on Stack Overflow

Mutable variables in Haskell?

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related