Episode 272: Inverses, Monoids and ∞

0:00Ben: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 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 the The inverse is an element of the set.

0:23Ben: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.

1:09Conor:How's it going?

1:10Ben:You know, alright, surviving.

1:12Conor:Surviving?

1:12Ben:You know, not not great, but but everything's okay. Just just the trials of life.

1:19Conor:The trials is this personally, or do you mean like the macro picture of the world?

1:23Ben:Uh oh, all of the above. Yeah. I've just come back from the just come back from the vet.

1:29Conor:Oh no.

1:29Ben:So it's nine o'clock in the morning here. I had to go to the vet early with one of my guinea pigs.

1:35Conor:Are they okay?

1:36Ben:Well, we'll see. They're at the vet, they're in an oxygen box.

1:41Conor:Oh no.

1:42Ben: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 their illnesses or maladies, right? They hide them. So by the time you notice like she only started going downhill last night, really.

2:00Conor:Oh wow.

2:01Ben:Took her in first thing this morning.

2:03Conor:I'm sorry to hear that.

2:05Ben:But uh, you know, hope for the best.

2:07Conor:Fingers crossed. Alright, all the listeners, send your best wishes to uh which which guinea pig is this?

2:15Ben:Because I know you have Magdalena is her name.

2:19Conor:Magdalena.

2:20Ben:She came with it. Maggie.

2:23Conor:Alright, well, hopefully we hear good news.

2:26Ben:Hopefully.

2:28Conor: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 McGonacle. But obviously no one called her called her that. We just called her Kit Kit. But she lived, I swear to God, it was like 19 or something. She was lived a very, very full life. So sad as it is.

2:53Ben:Well, guinea pigs live five plus years. Um generally they could they can on rare occasions they can even get to ten, but five to eight is about the ballpark.

3:05Conor:Yeah. Where is Magdalena at?

3:09Ben:Oh, she's young. We only got her last year, and I think she's not more than two.

3:14Conor:Oh no.

3:15Ben:You know, it's always hard to know how how exactly old how how you how old your pets are when you get them from rescue.

3:22Conor:Oh no.

3:22Ben:So this is definitely not like uh age-related, this is just a unfortunate uh No, this is a well hopefully it's a respiratory infection that she'll get over.

3:31Conor:Okay. Hopefully. Fingers crossed.

3:34Ben:Anyway.

3:35Conor:Transitioning, yeah. I mean That's all.

3:39Ben:Sorry to start with that.

3:40Conor:No, no. I mean I I it's I'd rather well, I wouldn't rather it be that, but uh I thought it was gonna be, you know, there's a lot of stuff going on in the world right now that uh, you know, it's not the focus of this podcast, but uh yeah, we'll still terrible.

3:56Ben:We'll save it for one night we're in the bar setting the world to rights.

3:59Conor: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.

4:08Ben:Oh, it's very cold up by you right now, is it?

4:10Conor:Yeah, it's uh snowy. It's been like minus seven in Celsius at like its warmest.

4:21Ben:At the warmest, okay. So I was gonna say minus seven on its own is not that cold. It's not that bad. But yeah, for a high, it's fairly cold.

4:28Conor: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 uh 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.

5:00Conor:And hard on the hands, very hard on the hands. And I don't even have the right that like the you're gonna 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 I wear two sets of those. It's fine once you get going. At minus 10 feels like minus 20. 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.

5:28Conor:Anyways, we've we've recently ordered a treadmill because I can't I can't do this.

5:35Ben:Indoor runs it's good. Nice to have the option.

5:38Conor:Yeah. Anyways, the this uh come brings up because we're talking about the state of the world and uh 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 gonna be for a couple days. But we were we were thinking like, well, I've never been to Florida, it's nice, but then we're like, well, isn't America really a place we wanna if we've got multiple options? Sure, it's close, but maybe fly a an extra hour or two and go somewhere else.

6:01Conor:Anyways.

6:04Ben:I've never been to Florida. Uh it is somewhere, it is one of the three states that Brits know about. The others being Texas and California.

6:16Conor:That's funny.

6:17Ben:They also know about New York, but as a city, not a state.

6:19Conor:Oh, I was gonna say, uh, I assume you know of New York, but I guess that's true.

6:22Ben:Uh no, I mean, I you know, I've lived in the US for over 20 years, so I know I know all the states, etc., but but the average Briton on the street, as we know from watching British TV, various game shows, they don't have they don't have a good grasp of US geography.

6:40Conor:Yeah, I wonder I wonder what percentage of folks in the UK can name a second city in New York.

6:47Ben:What would your guess in New York State?

6:49Conor:Yeah, yeah. What would what would your guess of that percentage be?

6:52Ben:In the general population, I don't know, low? Pretty low. Less than twenty percent, probably. Interesting. I don't know. Yeah, and I don't know which city it would be. Because maybe Albany?

7:07Conor:Yeah, I mean the three that come to mind when I think of other New York cities are Albany, Syracuse, and Buffalo.

7:13Ben:Oh yeah. Buffalo 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 I don't think they are. That's Princeton's i in Ithaca, right? Is that that is New York State, right?

7:31Conor:I thought Princeton was in New Jersey, to be honest. 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.

7:44Ben:Maybe it's not Princeton that's in Ithaca, maybe it's some other anyway, Ithaca is in New York, but yeah, Syracuse is one, but uh these are these are ones that I don't think would really know. Or they they they'll have heard of the city, but they won't associate it with being in New York State. Right. You're right, Princeton is in New Jersey. Why am I thinking of Ithaca? Well, it's a it's a college town anyway. Yeah.

8:11Conor:Anyways, what sho I sent you a 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?

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

8:48Conor:Alright. I mean this so first question. Have you uh did you listen to my last accidentally solo episode last week because I didn't reach out to you?

8:59Ben:Uh you better remind me of it. I did listen to it.

9:01Conor:It was basically talking about uh a couple algorithms and at the end combinators used to solve the mastermind game.

9:11Ben:Oh yeah, mastermind.

9:12Conor:So so the pure form of Wordle. Yes, which like 10 seconds or 30 seconds into my explanation of the game mastermind, I was like, ah, it's kind of like Wordle. And then I realized, oh wait, Wordle is just Yeah.

9:24Ben:Mastermind with extra constraints. Yeah.

9:26Conor:Yeah, mastermind with six guesses and words instead of colors, uh, 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.

9:54Ben:So there was like an analog so partial sum and adjacent difference.

9:58Conor:Yeah. And if you if you do the the my preferred, you know, more generic and pure uh version of adjacent difference that has n minus one elements in the result, you can't round trip. And I'm 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 Stepanov's motivation.

10:28Conor:And my uh 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 uh mathematics and quote unquote recreational uh uh 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 WeWA or one of these other array languages by inverting the plus scan.

11:03Conor:You get the exact behavior of adjacent difference, but then you also have the generic version of the map adjacent like from uh 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 Weewa, 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.

11:37Conor:And I 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-important 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 C20X feature.

12:02Conor:Anyway, so I I know that you are a huge proponent, so I put it on the list and I'm sure I'm sure we could easily talk about uh for 30 minutes or 60 minutes.

12:13Ben:Well, so I wanted to ask you, you said inverting plus scan. Is how do you mean by inverting? Is that is that built into the language? Is that a combinator or a a glyph that allows you to invert?

12:26Conor:Yeah, I in WeWa, though 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 an 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 uh is it iterator?

12:56Ben:Iterate, I think. Yeah. So that's the one you're thinking of. Where it's f of x, f of f of x, yeah, etc.

13:03Conor:Yeah. Okay. And there's this kind of slightly there's some nuances when you get to applying that to like a dyadic function, but we'll just focus on like the unary case here where you just got a 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.

13:32Ben:Okay, so that's inverting the function.

13:34Conor: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 an idiom or a primitive Oh, I see.

13:45Ben:So it has to support inversion.

13:48Conor: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 just explaining for the listener. They 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. Obverse? Obverse, yes. O-B-V-E-R-S-E.

14:23Conor:Obverse, 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.

14:53Conor:So it's a type of compaction, kind of like a filter zip width or enumerate kind of combined. 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.

15:43Ben:So the the property of inverse then is that it should be round triple. A function should be round triple with its inverse. Uh would you say that's a it if not a well, let's say it's a 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 if not stronger than that.

16:07Conor:Yeah, if it if that's not the correct 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 just its own inverse.

16:27Ben:But it's interesting because the temptation 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.

16:49Conor:I mean, I I know what you're saying, but for yeah, for the listener's sake.

16:52Ben: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 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 the The inverse is an element of the set.

17:15Ben: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.

17:35Conor:All right, so this is going back to category theory. So we're gonna have to slow down here for a sec.

17:39Ben:Really? I mean, I don't want to go a full category theory, but I'm just we're just talking about regular monoids and groups here. This is not this is not fully into you know total abstraction of category theory necessarily. And so then of course the first two monoids everyone learns, or well, one of the first couple of the first two are addition and multiplication, right? On the integers, right? And so and so up until that point in your life, probably you've when you come to that, you've thought of addition and subtraction as sort of inverse operations.

18:11Ben:But then when you learn about monoids and groups, and then you learn okay, an operate it's not necessarily the operation which is the inverse, it's that the uh 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 that is just I don't think that's true, right?

18:43Ben:Because it's not defined over the same set. You cannot divide by zero, right? And so so the multiplication, you know, and the rational number the rational numbers uh give uh inverses to some uh some elements of the set under multiplication, right? Or reciprocals do, right? But you can't you can multiply by zero, but you can't divide by zero.

19:10Conor:Well, folks, let's let's see if we can.

19:15Ben:So this is maybe beside this is maybe a different tangent to what you were asking, which is to say that it it's perfectly fine for functions to have inverses, right, in some sense, but we need to be careful. That's really the point.

19:31Conor:So I mean there this is gonna get into uh we'll share my screen, but we're we're gonna we won't make the mistake of making this unlistenable for the listener, which I did recently do on my other uh podcast, Tacit 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 I guess it's called undo, we're gonna get zero. So technically, this is mathematically incorrect.

20:08Conor:This is this is the inverse of plus yes is minus.

20:15Ben: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 of addition as subtraction. And and the reason you can do that is because they are defined precisely over the same sets.

20:31Conor:Well, so that's the thing. So watch, so we're gonna work our way to the ones where it's not defined. So if we if we switch our plus to a multiplies, I mean I guess we have to change these numbers. I guess this should be one, and this should- 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. It sh I was expecting this to say uh that this was a half.

21:05Conor:Well, what is is it called repeat? So uh I mean if we do I guess we need numbers here to oh yeah, because we have we have two. So right now what 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.

21:31Ben: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 sixteen.

21:44Conor:So this is division. Why did this not work? So we have we now have two times repeat negative one two, which is another way, if you say repeat negative one, that's another way of spelling undo. And this gives you what. So two multiplies inverse two, aka two divided by two is one. But if we switch it to one times undo, aka one multiplies inverse, it just gives us two. So this is confusing. But what I was working up to was if you go one times zero, you get zero.

22:21Conor:But what happens if you get one times undo, aka inverse? Well, this doesn't uh give me what I want either. So it just gives zero. So maybe there's something that says if I mean yeah.

22:35Ben:I mean this is computers. They're not sub they're not, you know, ints aren't integers, floats aren't real numbers. We're free to define things in computing. But it doesn't What I'm saying is it doesn't make it mathematically correct.

22:49Conor: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 yeah, 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.

23:14Ben:But so you've just written one divided by zero, and the answer is infinity. Yes. According to BQN. Which is clearly incorrect, but maybe pragmatic.

23:25Conor: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?

23:38Ben:I mean, can you ask BQN?

23:40Conor:Oh.

23:41Ben:He just said that it just said one divided by zero is infinity. Zero times infinity is not a number. Quite sen quite maybe sensibly. So So you know, we've just proved that multiplication and division are not inverses in BQN. Yeah.

23:59Conor:Infinity times infinity is infinity, and infinity divided by infinity was not a number.

24:08Ben:Right. Because a actually infinity itself is not a number, right? Mathematically speaking. Right. Or I suppose a different 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.

24:47Ben:So that's where my mathematical training ends, pretty much.

24:52Conor:I feel like just because someone's more formally trained or has taken more, you know, math courses in their life, though, it 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.

25:14Ben:Aaron Ross Powell Uh Above average for the general population, certainly. Above average for programmers? Maybe. I don't know. But yes. Back to the idea that just I you know, I think just by playing here, we've maybe discovered something. Or you've just you've discovered something interesting that was unexpected, maybe. I mean, I'm not a BQN user, but but but you you use this much more often. So you you you have some idea in your head of how it should behave.

25:43Ben:And some of the things we've just typed seem to have maybe surprised you a little. So that's that's great, right? Because who was it who said was it the Isaac Asimov who said, you know, the the beginning of learning the most the most exciting phrase in science is not Eureka, but that's odd. That's odd.

26:15Conor:Anyways, me reading the documentation in the middle of a podcast is probably not the best listening experience for the ADSP uh but anyways, yes, I 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? Uh not really. You're not always gonna have those when you're when you're playing around or having fun. Be sure to check these show notes either in your podcast app or at adspthepodcast.com for links to anything we mentioned in today's episode, as well as a link to a GitHub discussion where you can leave thoughts, comments, and questions.

26:59Conor:Thanks for listening. We hope you enjoyed and have a great day. I am the anti Bryce.

27:04Ben:Um