How do you develop algebraic thinking?

A few people have asked me how to develop Level 3 thinking. I'm not sure. But I've got some directions to try. In this episode, I go over 3 and a half ways to develop algebraic thinking.

Transcript

Eric Normand: How do you develop algebraic thinking? By the end of this episode, you should have three or maybe four different approaches to it. My name is Eric Normand. I help people thrive with functional programming.

I've been getting a bunch of questions along the lines of, "How do I develop level three thinking?" I'm writing a book. To do that, it's part of writing the book. It's a book about functional programming.

I'm trying to organize the material. Functional programming is a big, broad field. I have to choose what to teach and what not to teach. I've organized functional programming into three levels. I probably should call it functional thinking.

The first level is where you are able to distinguish actions from calculations and data. You can spot side effects. You're pretty good with immutability. You know how to solve problems without resorting to side effects like global immutable variables, things like that. You can move stuff around and isolate the calculation from the action, that kind of thing.

Level two gets a little bit more sophisticated. You're able to do higher order thinking. You're using higher order functions, higher order actions. You're using first class actions and even first class state if you need to. This lets you do stuff like data transformation pipelines with map filter and reduce, things like that.

Then there's level three which is what we're talking about today. This I'm calling algebraic thinking. I've also thought about calling it...Because algebraic thinking just brings up all sorts of questions like why algebra? This isn't high school math, those kinds of associations with the term algebra. It's about building composable models.

This may be a better way of talking about it but it's a third level where you're building very robust abstractions and basically algebras. Which I explained in the last episode so you should look that up.

I've been getting a bunch of questions about how to develop this. Now this whole show has been me exploring these ideas so that I can figure out how to put them into the book and so this is another exploration. I'm not sure. I don't know.

This part is the last part of the book. It is the part that I have worked on the least and so these are really rough. Which is cool, you get to see them really early.

Here are three approaches to self-study to get to level three. Here we go. The first one I'm going to bring up is property-based testing. You're probably familiar with unit testing or example-based testing where you give some arguments to a function and tell the system what to expect and that's your test. You give specific values.

In property-based testing you don't give specific values, those are generated randomly and you have to give a function basically that will tell the system whether the system under test got the right answer. This is called property-based testing because you're developing properties — like algebraic properties — that your function must obey, must uphold.

Let's just really quick because I don't want to teach property-based testing right now. I just want to give it as an example. If you were going to test the Sort function, like you write a new Sort, you could test that with two properties. One is that the returned list — you call Sort and you get a list back — that that list is in order.

There's another property you need which is that the return list is a permutation of the argument that you pass to Sort, the input list.

With those two properties you kind of covered the whole behavior of that function. You could test it with examples. You could give it the empty list. The empty list, sorting the empty list gives you empty list. Sorting a one gives you a one.

Sorting the list 2-1 gives you the list 1-2. You could give all the examples, but you never have to think higher order. You have somewhere in the back of your mind that it's got to be the same elements. You have somewhere in the back of your mind that it's got to be sorted when it comes out.

What you haven't thought about how to write that down. How do you actually write a test that says for any input list, the output list is in order? What does it mean to be in order? How do I test that it is actually in order?

Likewise, how do I test that this list is a permutation of another list? How do I write that down? Those kinds of thinking where you have to deal with not just a given list, but every list. Any list. Each and every list. That is the kind of thinking that gets you to that next level.

It's like first order logic. It's not just A and B, it's for all A. It's a different level of thinking. By doing property-based testing I think you really force your mind to go there, because it's all mental stuff. It's all mental skills. I'm not talking about some very concrete thing, it's all in your head.

Very related, that's number two, is algebraic properties. There's a lot of talk in the functional programming world about categories, category theory. This is similar reason to learn them, to learn categories as well as algebraic properties. Same idea.

They are very succinct truths about certain operations. They're expressed in very small formulas. They're relationships between a function and itself, or a function and another function. As an example, I could say a function F is commutative if F of A and B is equal to F of B and A.

To relationship, it's an equality, and it's of that one function F with itself. It relates how this function should operate in a totally abstract sense. We didn't say what A was. We didn't say what B was. We're basically saying for all A and all B that are valid arguments to that function, then this should be true.

We're thinking at a more abstract level, at an algebraic level, where you can start talking about F of A and B. You don't have to say F of one and seven, those are very specific numbers. You're talking about all numbers, A and B, or any numbers A and B.

It's the same thinking, but it's a different approach. You study algebra, you start to see that things can have meaning without being specific.

Addition, you can say A+B because you've been to algebra class. You sat through it, you did all the exercises, and now you get that there's stuff that you know about A+B, even though you don't know A or B.

That's the kind of thinking that you need to get, to get to level three. Another one, the third one. This one is much more difficult material, but it is material. It is something I can link you to that you can watch. Whereas, the other two are a little bit more general concepts.

The third thing is called denotational design. This is basically some talks and some papers by Conal Elliott. He's big in the Haskell community. He gave a really good talk. It's like a workshop. It's 2 hours and 20 minutes of him stepping through his thought process, which he calls denotational design for building a graphics system.

I've watched it many times. [laughs] I think that that is the best resource available for understanding the mindset from first principles designing something like that. Some notable things about it. The first one is that he's working with the type signatures of the functions.

The function signatures, what arguments does it take, what does it return, totally never shows a single implementation of what an image is. The fact that he can walk through slide after slide of code with no implementation. He's just showing the function signatures. That is the level you need to get to.

I have a whole thing on types which I'm about to say after I finish with denotational design. I'm not saying you need types. I'm not. What I'm saying is that he was thinking at the level of this function does this. I can talk about it and how it behaves without showing the implementation.

He starts from first principles, he builds a type for the image, what is an image, and then he starts showing how you could implement a combinator that acts on the image. How do we overlay two images? How do we have a mask where a shape, a region is shown through and then the rest isn't shown?

How do we add a background color, a certain transparent color? All these operations he does show how they are simply implemented, as long as you have this very simple notion. Simple, but elegant simple. It's a very elegant notion of what an image is.

You never know how he'd implemented image, which is where you need to get to. You need to be able to think about the operations on image, without thinking about the concrete implementation. In his system, an image isn't an array of pixels because you've already limited yourself to a certain representation.

He has said, "Let's not even implement it yet, so that we can talk about the kinds of operations we want to be able to do in the abstract." You notice I'm trying to get at something almost ineffable without using the term algebra. [laughs]

With all these three examples, the property-based testing, the algebraic properties, the denotational design, you're able to think about the system without caring about how it's implemented. That's the algebra part. You're thinking in this static reasoning. You can look at the expressions that you can build out of this algebra and reason about them.

A couple of people asked if this was something that types help with. I mentioned that Conal Elliott uses the types to talk about functions without having to implement them. I don't want to get into the typed versus untyped debate. Not in this episode. I don't think that types are necessary in the language you write them in. I think that this is all stuff that's happening here.

What the types do help you with though, if you used a strongly typed language, a statically typed, strongly-typed language, like Haskell, what you get is the discipline for free. You are forced to internalize the type system. What you're internalizing that helps is a few things that helps with this kind of thinking. One is the case-based thinking.

In Haskell, if you have multiple cases in your algebraic data type, there's a warning or you can turn it into an error if you forget on your cases. I suggest turning it into an error so you always have to deal with all the cases.

What that makes you do is make sure that you're covering the whole thing, that you create a total function. At least it helps. It makes you think about that. I'm going to make this function work for all values of this type. That is something that I see people not doing in the untyped world that they could learn better from. They'll have to do it themselves [laughs] with internal discipline. Sit and really make sure that all the bases are covered.

The function works for all values because you don't want corner cases. That messes up your algebra. Another thing is pushing information into the type. What do I mean by that? Some functions don't work for negative numbers. There's no built-in type in Haskell for non-negative numbers, but you can make one and it wouldn't be hard. It's a common exercise to do. It's a few lines. Then you have this type that represents non-negative numbers.

What is a little harder and speaks to the level three thinking — algebraic thinking — is to realize that when you're using that type you don't really need to care where it came from. It came from somewhere.

When I'm programming this function, when I'm implementing this function and it has that type, it's a function that takes a non-negative integer, I don't have to care where it came from. I'm not thinking about that. I just know that this type guarantees x, y, z.

I'm pushing that information into the type. That kind of encapsulation is also part of it. That I don't really have to worry about where it comes from. I can let that be for now. I'm encapsulating that knowledge. This function's functionality.

Conal Elliot once said that one of the cool things about numbers and one of the reason why they're so useful is if you have the number seven, you can't know how you got that seven. You don't know if it was 3+4, or 5+2, or 1+6, or 14*0.5, or whatever. You don't know where it came from. It's equal to every other seven, regardless of where it came from.

That's it. That's level three. [laughs] I don't know how else to say it. If you're thinking in those terms, I don't care where this come from, I don't care how it got generated, that is level three.

To bring back the video example, I've been developing this example over several episodes. When I'm concatenating two videos, I don't care where the videos came from. I want to be able to concatenate them, regardless of where they came from. I shouldn't care. That is what I'm talking about, where you don't care where it came from.

If you start in the wrong place, you could say, "Well, a video is a file on disc that has a sequence of frames." Now when I'm developing concatenate, I brought all of this concrete stuff to concatenate. I might think, to implement concatenate, I open up a new file, copy the existing frames, and then add the other frames to the end of it.

You've already lost the abstract game. We do that. Before level three, we do that way too much, where we're actually thinking about how to implement it way too fast. Way before we've thought about, what should it mean, what should it do, how does it relate to the other operations that are allowed.

This is a thing that I've experienced in Haskell where, if the type starts getting complicated, then you know you've got a problem. If you've got seven fields on your type, now there's something wrong. You're not really doing this kind of algebraic thinking.

The type has become too complex, it's going to be impossible to do this kind of smooth, elegant algebra anymore. When you push information into the type, you got a signal for how complex the thing is. That's really all I've got about to how to get to level three.

Part of it is pointing at it. Trying to point out to people who are not there and part of it is to try to use things that are there that you could go learn right now that will help you, that will help you get the ideas to get there.

My challenge as the author of the book that's trying to get people there is to come up with good examples, good scenarios where this is useful. [laughs] It's not just some abstract notion and also the exercises will get you there. You could see the benefit because it is a feeling. It's not something. There's a gray line that you cross.

At some point, you think, "Wow, this is a really solid algebra. No corner cases, very small and elegant. I can think abstractly about it." It's just some invisible line that you cross at some point.

If you like this episode, you can find all the old past episodes at lispcast.com/podcast. There you'll find audio, video, and text versions of all the episodes. You'll also find links to subscribe whether it's on your podcast player or YouTube or however you want to consume it. Also links to social media where you can get in discussion with me.

That's all I've got. This has been my thought on functional programming. I'm Eric Normand. Thank you for being there and rock on.