Algorithms + Data Structures = Programs - Episode 272: Inverses, Monoids and ∞

Episode Date: February 6, 2026

In this episode, Conor and Ben chat about algorithms inverses, monoids, infinity and more!Link to Episode 272 on WebsiteDiscuss this episode, leave a comment, or ask a question (on GitHub)SocialsADSP: The Podcast: TwitterConor Hoekstra: LinkTree / BioBen Deane: Twitter | BlueSkyShow NotesDate Recorded: 2026-02-04Date Released: 2026-02-06ADSP Episode 271: Mastermind AlgorithmsHoogle Translate adjacent_transformHoogle Translate scanHoogle Translate whereBQN ⁼ (undo)Tacit Talk Episode 30:Intro Song InfoMiss You by Sarah Jansen https://soundcloud.com/sarahjansenmusicCreative Commons — Attribution 3.0 Unported — CC BY 3.0Free Download / Stream: http://bit.ly/l-miss-youMusic promoted by Audio Library https://youtu.be/iYYxnasvfx8

You know, when we think about folds, it comes up with folds and unfolds and things like that. You think about monoids, right? And you think about the addition over the integers, let's say, right? And then you think what's the inverse of addition? Well, you think subtraction, but it's really the same thing as addition, just with the negative numbers, I guess. And so from there you get the idea of like the inverse is an element of the set. It's not a function, right? So there's that.

Maybe that's not what you were asking, but there's something else that just occurred to me. Like if we're talking about monoids and then extending that to semi-groups and groups, then the idea of an inverse is not that you have an inverse operation, but that you have inverse elements in your set for the operation. Welcome to ADSP, the podcast, episode 272 recorded on February 4, 2006. My name is Connor, and today with my co-host, Ben, we chat about algorithm inverses, monoids, infinity, and more. How's it going? You know, all right, surviving. surviving you know not not great but but everything's okay just just the trials of life the trials is this personally or do you mean like the macro picture of the world uh oh all of the above yeah i've just come back from the just come back from the vet oh no so it's nine o'clock in the

morning here i had to go to the vet early with one of my guinea pigs are they okay well we'll see they're at the vet they're in an oxygen box oh no So with guinea pigs, it's always a bit, they're very, they can be very fragile. And because they're prey animals, they don't, they don't show their illnesses or maladies, right? They hide them. So by the time you notice, like, she only started going downhill last night, really. Oh, wow. Took her in first thing this morning.

I'm sorry to hear that. But, you know, hope for the best. Fingers crossed. All right, all the listeners send your. Best wishes to which guinea pig is this, because I know you have. Magdalena is her name. Magdalena. She came with it.

Maggie. All right, well, hopefully we hear good news. Hopefully. Yeah. My family's cat passed away a few months ago, but, I mean, she went by, I think her official name was Professor Minerva, McGonical, but obviously no one called. Right. called her that. We just called her Kit Kit. But she lived, I swear to God, it was like 19 or something.

She was, yeah, yeah. Lived a very, very full life. So as sad as it is. Well, guinea pigs live five plus years. Generally, they could, on rare occasions they can even get to 10, but five to eight is about the ballpark. Yeah. Where is Megdalene at? Oh, she's young. I only got that last. year and I think she's not more than two. Oh no. You know, it's always hard to know how exactly old, how old your pets are when you get

them from rescue. Oh, no. So this is definitely not like age-related. This is just an unfortunate. No, this is a, well, hopefully it's a respiratory infection that she'll get over. Okay. Hopefully. Fingers crossed.

Anyway. Transitioning, yeah. I mean. That's all. Sorry to start with that. No, no. I mean, I'd rather, well, I wouldn't rather it be that, but I thought it was going to be, you know, there's a lot of stuff going on in the world right now that, you know, it's not the focus of this podcast,

but, yeah. Yeah, well. It's all terrible. We'll save it for one night we're in the boss and the world to write. Yeah, yeah. Hopefully everything turns out fine. Shima was talking about, I don't know, potentially trying to escape the snow, which we may or may not do. Oh, it's very cold up by you right now, is it?

Yeah, it's... It's been... It's been, like, minus 7 in Celsius at, like, it's warmest. At the warmest, okay, so... At the warmest. Minus 7 on its own is not that cold. It's not that bad. But, yeah, for a high, it's fairly cold.

And it's been like that for two weeks, I'd say, and there was this crazy snowfall that happened to, like, all of the, whatever, northeastern North America. And so there's... I literally shoveled the snow like three or three or four times this one day when it snowed like, I don't know, three feet or something. And then it hasn't really snowed a lot since, but it's been very cold and it's been very demoralizing trying to run outside when it's like usually it's typically like minus 10 feels like minus 20. It's hard on the hands. Very hard on the hands. And I don't even have the right, like the, you're going to be like, why not just buy a good set of gloves?

I have two like dollar store, you know, just like the cotton, like. So I wear two sets of those. It's fine once you get going. At minus 10 feels like minus 20s. Once you hit like the two kilometer mark, it's just the first two kilometers where you're like scrunching your hands to get the blood flowing. Anyways, we've recently ordered a treadmill because I can't, I can't do this. Indoor runs. It's nice to have the option.

Yeah. Anyways, this brings up because we're talking about the state of the world, and we were trying to look at options, and this may or may not even end up happening. And if it does, it's probably only going to be for a couple days. But we were thinking, like, well, I've never been to Florida. It's nice. But then we're like, well, this is America really a place we want to. If we've got multiple options, sure, it's close, but maybe fly an extra an hour or two and go somewhere else. So anyways.

I've never been to Florida. It is somewhere, it is one of the three states that Brits know about. The others being Texas and California. That's funny. They also know about New York, but as a city, not a state. Oh, I was going to say, I assume you know of New York, but I guess that's true. No, I mean, you know, I've lived in the U.S. for over 20 years, so I know all the states, et cetera. but the average Britain on the street, as we know from watching British TV, various game shows, they don't have a good grasp of US geography.

Yeah, I wonder what percentage of folks in the UK can name a second city in New York? In New York State? Yeah, yeah. What would your guess of that percentage be? In the general population, I don't know, low, pretty low, less than 20% probably. Interesting. I don't know. Yeah, and I don't know which city it would be because maybe Albany?

Yeah, I mean, the three that come to mind when I think of other New York cities are Albany, Syracuse, and Buffalo. Oh, yeah. I didn't even think of Buffalo. Buffalo has a football team. I was thinking of maybe like university towns like Ithaca. But I don't think they are. That's, for instance, in Ithaca, right? That is New York State.

Right? I thought Princeton was in New Jersey, to be honest. So now I said that, I did too. I feel like there was some scene I saw in Oppenheimer or something I read in a book that gave me the impression that Princeton was in New Jersey. Maybe it's not Princeton that's in Ithaca. Maybe it's some other.

Anyway, Ithaca is in New York. Yeah, Syracuse is one. But these are ones that I don't think Brits would really know or they'll have heard of the city but they won't associate it of being in New York State. Right. You're right.

Princeton is in New Jersey. Why am I thinking of Ithaca? Well, it's a college town anyway. Yeah. Anyways, I sent you a number of things that I wanted to chat about. Where should we start? Or do you have things you want to chat about too?

Well, one of the things you said, let's see here. I always love to talk about recreational math, recreational algorithms. that kind of thing because I think that's so important. You know, playing is so important to me throughout my life and still in my professional life. Just the idea of playing with code, seeing what's possible, trying things out. So I think we should talk about that. All right.

I mean, this, so first question, have you, did you listen to my last accidentally solo episode last week because I didn't reach out to you. You better remind me of it. I did listen to it. It was basically talking about a couple algorithms and at the end, combinators used to solve the mastermind game. Okay.

Oh, yeah, mastermind. So the pure form of wordl. Yes, which like 10 seconds or 30 seconds into my explanation of the game, Mastermind. I was like, ah, it's kind of like Wardle. And then I realized, oh, wait, wordal is just... Yeah, Mastermind with extra constraints.

Yeah, Mastermind. with six guesses and words instead of colors with the constraint that it has to be a valid word. And there's the exact matches and the near matches. And the point of that ramble was just my realization that the motivation for the adjacent difference or the motivation for, yeah, adjacent difference in C++98 was Stepanov wanted two algorithms that could round trip. So there was like an analog. So partial sum and adjacent difference.

Yeah. And if you do the my preferred, you know, more generic and pure version of adjacent difference that has n-minus-1 elements in the result, you can't round-trip. And I remember I mentioned Christabella, who I actually don't know if he still works at Google, but I believe at the time was working at Google when we were chatting about this and probably still does. And he was kind of taking the stance that it is the correct implementation of it. because that was Steppenov's motivation. And my feeling is that it shouldn't, even though that is a, I understand the motivation, it shouldn't have been a motivation. It should have been this more generic form.

And this ties back into recreational mathematics and quote unquote recreational algorithms, which isn't actually a term, but I just borrowed it from math and, you know, ported it to algorithms. Sure. is that my realization that the you can get adjacent difference with an inversion modifier in Wiiwa or one of these other array language is by inverting the plus scan, you get the exact behavior of adjacent difference, but then you also have the generic version of the map adjacent like from Haskell, which I want. You get both of those in an array language, but my realization of that came from the mastermind kata, which like I have a GitHub repo. I've implemented

it in like, I don't know how many different languages. And for reasons that don't matter, I was redoing it in Wii. And then I had this like realization. And then it made me think that we don't really talk about, I mean, we have at times, but this idea of what you just said, like playing around. And I even submitted, I think, once or twice the talk recreational algorithms. And every time it's been rejected. Because like, what is the description of that talk, you know, showing how, you know, small trivial problems, you know, that are non-importants can lead to important insights. Like, a lot of people see that and they're like, where's the, you know, I need something about a unit testing framework or I need something about the latest and

greatest C++20x feature. Anyway, so I know that you are a huge proponent. So I put it on the list. And I'm sure we could easily talk about for 30 minutes or 60 minutes. Well, so I wanted to ask you, you said inverting plus scan. How do you mean? by inverting. Is that built into the language? Is that a combinator or a glyph that allows you to invert? Yeah. In Wiwa, though, how does that work? One of the more recent languages, they call it a modifier, and I believe most languages call them modifiers now. It's not exactly a combinator. So most array languages have something, an operator or a modifier, which is you can think of as a higher a higher order function called power or repeat,

which takes a function and then an integer, and it'll repeat that. So I think in Haskell there's a iterator. It's a right, I think. So that's the one you're thinking of where it's F of X, F of F of X, etc. Yeah.

Okay. And there's this kind of slightly, there's some nuances when you get to applying that to like a diatic function. But we'll just focus on like the unary case here where you just got one argument function, you know, you're squaring something. If you do it three times, it's now whatever, squared three times. And most array languages have the ability to call power or repeat with negative one, which is kind of... I see. Okay, so that's inverting the function. Yeah. And I talked about this with Bryce once and he was like, well, how does that work? And it's really just like

implementation defined, right? So if a idiom or a primitive... Oh, I see. So it has to support inversion. Yes. Okay. And in the J language, which was created in 1990, kind of APL 2.0, it's the ASCII version of APL. I know you know this. I'm explaining for the listener. They introduced the power operator and inverse. And then they also provided something called obverse, which gives you the ability to define an inverse for a function that you've written. So, okay. It's, I don't actually know what you call that.

Did you say obverse? Obverse, yes. O-B-V-E-R-S-E. Abverse, yes, was the primitive that they added so that you can define your own inverse. So, I mean, this is a little bit of a hack for an aggressive term, because I really, really like. the inverse behaviors that are implemented like another one

that I've pointed out or brought up on the show before is one of my favorite primitives in array languages is called where or indices it given a sequence

of ones and zeros it'll return you back the indices that correspond to the ones so right you know it's a type of compaction kind of like

a yeah a filter zip width or enumerate kind of combined and And if you do an inverse on that operation, on a list of sorted numbers,

you get back the mask that would generate that for you. And then there's a lot of like, you know, kind of hand-waving is like, well, technically, what if there's a bunch of zeros at the end of an array? Like, you can't deterministically one-to-one always get the same results. So there's certain things where people are like, well, if you want to be really like academically correct, you shouldn't have an inverse on this

because you don't have these like total functions or whatever you call them. So the property of inverse then is that it should be round-trippable. Functions should be round-trippable with its inverse. Would you say that's a, if not a, well, let's say it's a property to be desired. It might not be the case for every implementation, but I'd imagine it's certainly, in the guidelines. Yes. It's not stronger than that.

Yeah, if that's not the correct, yeah, academic definition, it's from a understanding point of view, definitely the essence of it. So there's a lot of functions that have their inverses implemented as just themselves. You could think of a couple, right? Like reverse is. Yeah, sure. It's just its own inverse. But it's interesting because the temptation, so this is interesting because there's a temptation sometimes to say things

like division and multiplication are inverses, which is, of course, not true, because they are defined over different things fundamentally. We'll expound on that. I mean, I know what you're saying, but for the listener's sake. You know, when we think about folds, it comes up with folds and unfolds and things like that. You think about monoids, right? And you think about the addition over the integers, let's say, right? And then you think, what's the inverse of addition?

Well, you think subtraction, but it's really the same thing as addition, just with the negative numbers, I guess. And so from there, you get the idea of, like, the inverse is an element of the set. It's not a function, right? So there's that. Maybe that's not what you were asking, but there's something else that just occurred to me. Like, if we're talking about monoids and then extending that to semi-groups and groups, then the idea of an inverse is not that you have an inverse operation,

but that you have inverse elements in your set for the operation. All right, so this is going back to category theory, so we're going to have to slow down here for a sec. Well, not really. I mean, I don't want to go full category theory. We're just talking about regular monoids and groups here. This is not fully into total abstraction of category theory, necessarily. And so then, of course, the first two monoids everyone learns all,

well, one of the first, a couple of the first two are addition and multiplication, right? on the integers, right? And so up until that point in your life, probably when you come to that, you've thought of addition and subtraction as sort of inverse operations. But then when you learn about monoids and groups, then you learn, okay, it's not necessarily the operation,

which is the inverse, it's that the members of the set have inverses under this operation. And so, you know, if you don't take that view and you continue to try and think of functions as having inverses, then it can lead you to think about things like, well, division is the inverse of multiplication.

And that is just, I don't think that's true, right? Because it's not defined over the same set. You cannot divide by zero, right? And so multiplication, you know, and the rational numbers give inverses to some, some elements of the set under multiplication, right? Or reciprocals do, right? But you can multiply by zero, you can't divide by zero.

Well, folks, let's see if we can. So this is maybe a different tangent to what you were asking, which is to say that it's perfectly fine for functions to have inverses, right, in some sense, but we need to be careful. That's really the point. So, I mean, this is going to get into, we'll share my screen, but we won't make the mistake of making this unlistenable for the listener, which I did recently do on my other podcast, Tasset Talk. I forgot that some people listen to these things, audio only. So, I mean, if we go to BQN and we do, you know, one plus one, we get two.

but if we do one or I guess it's called undo we're going to get zero so technically this is mathematically incorrect this is this is the inverse

of plus yes is minus so it happens in this case that you can you can do that right that's what I'm saying it's fine

yes you can look at the inverse addition as subtraction and the reason you can do that is because they are defined precisely over the same sets. Well, so that's the thing. So we're going to work our way to the ones where it's not defined. So if we switch our plus to a multiplies,

I mean, I guess we have to change these numbers. I guess this should be one. So it's one times two is two. But if we do one times undo two, then you would expect half is what. Oh, yeah, you would expect. half, but it's giving you two. That doesn't make sense at all.

I was expecting this to say that this was a half. Well, what is, is it called repeat? So, I mean, if we do, I guess we need numbers here to, oh yeah, because we have two. So right now what I'm showing is I have one times repeat two, two, which is just confusing. It gives two. Although, I guess that makes sense, yeah. And then we have two times repeat two, two, that gives eight because you're multiplying. So the times repeat two is two to the power of three.

Is two multiplies. So that's squaring it twice. If you take two and square it twice, no, not squaring it twice. That would get 16. So this is division. Why did this not work? So we now have two times repeat negative one, two. which is another way, if you say repeat negative 1, that's another way of spelling undo.

And this gives you 1. So 2 multiplies inverse 2, aka 2 divided by 2 is 1. But if we switch it to 1 times undo, aka 1 multiplies inverse, it just gives us 2. So this is confusing. But what I was working up to was if you go 1 times 0, you get 0. but what happens if you get one times undo, aka inverse? This doesn't give me what I want either. So it just gives zero.

So maybe there's some thing that says if... I mean, yeah. I mean, this is computers. They're not, you know, ints aren't integers, floats aren't real numbers. We're free to define things in computing. What I'm saying is it doesn't make it mathematically correct. It makes it practical, perhaps. That is exactly the word.

So there is this pragmatic versus... What is the word that Marshall, the implementer of BQN? We'll use the word like mathematically correct or academically correct. And some of these array languages choose to do things that are more pragmatic or practical in terms of increasing the usefulness of a primitive. So you've just written 1 divided by 0, and the answer is infinity? Yes. According to BQN.

Which is clearly incorrect. but maybe pragmatic. Yeah, so anyways, I'm confused. I will report back to you in the future. Why, when any... Well, so what's zero times infinity? I mean, can you ask EQA? Oh.

It just said that... It just said one divided by zero is infinity. Zero times infinity is not a number. Quite, maybe sensibly. So, you know, we've just proved that multiplication and division are not inverses in BQN. Yeah. Infinity times infinity is infinity, and infinity divided by infinity was not a number. Right.

Because actually, infinity itself is not a number, right? Mathematically speaking. Right. Or I suppose maybe a different kind of number. I don't know. You should know that, by the way, all of my. basically all of my mathematics is recreational at this point in my life. For some reason, people see my talks and they think I know mathematics. But in fact, most of them have more

mathematical training than me in a formal sense. I didn't want to do more differential equations than I needed to at university. So that's where my mathematical training ends pretty much. I feel like just because someone's more formally trained or has taken more, you know, math courses in their life, though, doesn't necessarily equate to later in life. I would imagine that the amount that you have retained and actively, like, think about in the background is probably above average at a minimum. Above average for the general population, certainly. above average for programmers, maybe, I don't know. But yes, back to the idea that just, you know, I think just by playing here, we've maybe discovered something,

or you've discovered something interesting that was unexpected, maybe. I mean, I'm not a BQN user, but you use this much more often. So you have some idea in your head of how it should behave, and some of the things we've just typed seem to have maybe surprised, so that's that's great right because who was it who said was it Isaac Asimov who said you know the beginning of learning the most the most exciting phrase in science is not eureka but that's odd that's odd anyways me reading the documentation in the middle of a podcast is probably not the best listening experience for the ADSP uh dead air man dead air

But anyways, yes, I was expecting the BQN to, for one multiplies inverse of zero to give infinity. But it does not. So we indeed did learn something. Was it an algorithmic insight? Yeah, not really. You're not always going to have those when you're playing around or having fun. Be sure to check these show notes, either in your podcast app or at ADSP the podcast. for links to anything we mentioned in today's episode, as well as a link to a get-up discussion where you can leave thoughts, comments, and questions.

Thanks for listening. We hope you enjoyed and have a great day. I am the anti-brace.