Algebraic Properties and Composition

This is an episode of Thoughts on Functional Programming, a podcast by Eric Normand.

Subscribe: RSSApple PodcastsGoogle PlayOvercast

In school, we learn about a few algebraic properties. These apply very well in functional programming because their expression is so simple, their definitions are so simple and they really focus on how things compose.

Transcript

Hello, my name is Eric Normand, and these are my thoughts on functional programming. The thought I was having was about composability and algebraic properties.

In school, we learn about a few algebraic properties, we learn about commutativity, we learn about associativity, we learn about the identity of addition, which is zero and the identity of multiplication, which is one.

https://twitter.com/ericnormand/status/1023221639838949376?ref_src=twsrc%5Etfw

These apply very well in functional programming, I think not so much because they are mathematical ideas, but more because their expression is so simple, their definitions are so simple that they really focus on how things compose.

What mathematicians have done is figured out a bunch of ones for mathematical operations like addition is associative and commutative, multiplication likewise. When you have that, you have these very simple ways of saying how addition composes with itself.

Now, when we're building abstractions in a functional language, where because our primary means of building a program from smaller parts is composition, we want to focus on how things compose first and foremost.

https://twitter.com/ericnormand/status/1063461939576213504

I believe it's important to define upfront how things compose before you implement the thing. What do I mean by that?

I would say that if you want to define an operation, let's say, I have an example that I gave in a presentation that is, you want to define a way to rotate an image and also translate the image, move it around on the screen.

You want to define how they compose, thus translate and then rotate. Is that different from rotate then translate? What if I do two rotates or two translates? How do they affect each other?

By thinking that through before you start implementing the thing, and even battening those things down with testing, then you will be able to...You can guarantee upfront that they compose in the way you're expecting.

Now, mathematical definitions, mathematical properties are not going to give you everything you need because they're kind of analyzing existing properties of existing operations.

They're not engineering, they're not designing new operations so much. What you want to be able to do is take the lessons from those algebraic properties and the lessons that are the most important are that they have very simple expressions.

https://twitter.com/ericnormand/status/1008364120889069568?ref_src=twsrc%5Etfw

You can do, with one or two...This expression is usually an identity meaning an equality. You say rotate then translate is equal to translate and then rotate or you say for idempotence, A or F(A)=F(F(A)). You're saying how it composes with itself with multiple invocations in the same operation.

What this let's you do is, these are simple ones, but you can define new ones because there's no algebraic property that...There's few algebraic properties that relate to. There's like the reverse or the inverse, something like that. We got to cross the street.

There aren't as many as we would want, but what's important is that it's simple, that it's a very short expression, and that it defines how things work. The other thing that you can play a little bit looser with is the notion of equality because, very often, in software we use an if statement to reduce the scope of when something is applicable. What do I mean by that?

In general, adding an item like a key value pair to a hash map is not commutative so the association operation enclosure is not commutative because if you add the same key, if you add the key A with a value one, and then you add the key A with the value two, the two will overwrite the one. The order matters. Whichever one comes second, that's the one that gets kept.

https://twitter.com/ericnormand/status/1017061274604179456?ref_src=twsrc%5Etfw

They're not strictly equal, but you can say, "Well, I know in general that's true, it's not commutative, but in this particular case, I know that I'm never going to collide keys." You can make that assertion that's kind of like a run-time assertion that, in this case, I will never collide keys.

Then, it becomes commutative again because if you never collide keys, you never have that overwrite situation. Then, again, it doesn't matter what order you put stuff in. Another thing you can do is you can say they might not be equal, but they're still both valid, they're still both correct. If I do A=1 and then I do A=2, so the result is A=2 is stored in that map.

I could say that's a valid result, but also I could say A=1 was a valid result as well. That can happen too where you're not comparing them on strict equality, but on something else like there there is no contradiction. They're both equivalent.

Like, for instance, the timestamp. Sometimes, you don't care about the exact timestamp, you just want to know that it's after a previous one. That's a way of saying it's consistent, it's valid, they don't have to be equal, strictly equal, like that.

There's ways of of using these properties where they're not strictly defined the way they are in mathematics, that they can be defined a little bit more loosely, that two things could be commutative modulo. I know that there's no key collisions or modulo the timestamps don't matter or modulo they are both consistent.

I'm probably going to talk more about algebraic properties. I just wanted to get that idea quickly out there. Thank you so much, hit subscribe, and I'll see you later, bye.