0
$\begingroup$

IIUC, category theory only applies to immutable objects, and mutability is modelled within that using e.g. functors, monads. Is that true? If so, why doesn't category theory include immutability? Has no-one got round to adding that, or is it impossible?

I'm asking because I've never seen category theory applied to, or discussed in the context of, imperative code or languages, and I want to know if it can be.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

It is not true. The state monad expresses mutable state that can be used in a computation, and that is just one example.

A second example is Frank Oles's PhD thesis, supervised by John Reynolds, where a presheaf model of Algol, a procedural language with mutable variable, is given. This work was subsequently extended and adapted.

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ I'm used to the state monad being s => (s, a), which isn't mutable in the sense that a particular section of memory is modified. Have I misunderstood sth? $\endgroup$
    – joel
    Oct 6, 2022 at 23:00
  • 1
    $\begingroup$ s is (the type of) memory. $\endgroup$
    – Andrej Bauer
    Oct 7, 2022 at 7:16
  • $\begingroup$ do you mean the implementation in functional languages, where a new value is created rather than the original mutated, is just one implementation of s => (s, a), and an imperative one would also be valid? See also my question edit $\endgroup$
    – joel
    Oct 8, 2022 at 14:40
  • $\begingroup$ No, I mean categorical models of procedural languages. The state monad is just the simplest example to understand. I provided another reference to dispell any doubts. $\endgroup$
    – Andrej Bauer
    Oct 8, 2022 at 20:04
  • $\begingroup$ OK, thanks. In that case my next question (which I'm not asking you to answer) is why do we say functional programming enables composition if category theory also applies to procedural languages? $\endgroup$
    – joel
    Oct 8, 2022 at 20:29

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.