Algorithms + Data Structures = Programs - Episode 45: Algebraic Groups and Birds!

Episode Date: October 1, 2021

In this episode, Bryce and Conor talk about inverse scans, groups and combinator birds!Date Recorded: 2021-09-11Date Released: 2021-10-01Canada Wide Science FairADSP Episode 43: Parallel Scans and AssociativityADSP Episode 44: Should You Drop Out of School?Inverse Scan ExampleAndreas Schätti TweetADSP Github RepoSunbubble ADSP Issue on GroupsAlgebraic GroupTo Mock a MockingbirdLambda CalculusSKI Combinator CalculusList of Combinator BirdsIntro 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

We got warblers, we got cardinals, we got golden eagles now. I do love birds and waterfowl, so. Yeah, oh my goodness, that's correct. That's correct. Bryce, I wasn't even thinking about that. Welcome to ADSP, the podcast episode 45 recorded on September 11th, 2021. My name is Connor, and today with my co-host Bryce, we revisit inverse scans, talk about groups, and talk a little bit about combinator birds. Maybe that should be an episode one day. Not that people care. Maybe not. I went to three national science fairs.

Yeah, that's definitely going to be an episode. do i not i i keep learning things about connor and you know it's i've learned enough surprising things about connor that i'm never surprised when i learn some new savant level thing that connor has done it's not savant although Although I will say this, the start of the story was that I had no intention on trying to get to the national level. I just one year, I asked my mom, how come when people break their spinal cords, they can't like fix it like you break your arm, you put a cast on it, you're good to go. But like you break your spinal cord. And then you're in a wheelchair for the rest of your life either as a paraplegic or quadriplegic and uh she was like well why don't you do a science fair project on it and uh fast forward like a couple years later i had finished cutting up some worms and like testing how they regenerated their cells and all this stuff and i was just this like happy-go- I had, I had, uh, finished all my projects in a woodworking elective. And so I cut out like a sort of mini life-size human, and then plugged in a bunch of Christmas lights to like different parts of the body. And very,

very unsafely had this mechanism where I could plug and unplug these little things. And so it would light up like, Oh, if you break it at l4 like at lumber 4 like this is the parts that you lose access to it was super awesome and definitely against all the regulations uh and then any i ended up i ended up getting one of the top awards which involved a entrance to the canada-wide science fair which at the the time was that year being held in St. John's, Newfoundland on the other side of the country. Connor Hoekstra in grade eight had never stepped foot on a plane before. I had not, I had not traveled like outside of the province. I don't think in my lifetime, maybe I crossed the U S border once, but I'd never flown, um, never been on a plane. Well, I guess those are the same thing, but you never know.

And so I was so excited. I walked down the whatever the stage, the auditorium down to the stage. I was literally like shaking and jumping up and down. And all I was thinking in my head, like literally all the other winners, they're just standing there with their like trophy. I am like bouncing up and down on the stage like a small bunny rabbit, like an Energizer bunny. And in my head, I'm thinking, oh, my God, I hope my parents let me go. Oh, my God, I hope my parents let me go because I wasn't sure if I was going to be allowed to go. But it was all expenses paid.

And, yeah, that was a good time. They fly your parents out too, I assume. No, no, no. You, uh, you go with the chaperone. Um, and yeah, Chris Gayski, uh, he, he did his on a genetics project on genetics at the time. And so, yeah, we became good friends. Um, and I was supposed to go travel around with him in Europe. He was doing his MBA in the Netherlands in the past year. And then good old COVID. Good old COVID. He was doing an MBA in the Netherlands in the past year. And then good old COVID.

Good old COVID. He's doing an MBA in the Netherlands? Yeah, yeah. He is. It would have been awesome to go and travel around. But well, so we ended up talking a little bit about the associative operation back in episode 43. Then episode 44, completely unplanned. We just ended up opining.

We might have to do another episode. I think the moral is if you're in school, 43, then episode 44, completely unplanned. We just ended up opining. We might have to do another episode. I think the moral is if you're in school, probably the answer for most of you is to stay in school. Should you go to school? Stay tuned for a future episode, which I guess at that point will be planned. I was going to bring up one last thing, which maybe I should cut into the first one because it's math related. So we we in episode 42 had you had mentioned there's probably a name for the mathematical property of the difference between the plus and the max scan. And then we put it to our listeners.

So one of our listeners responded via tweet. His name or their name, I should say is andre andreas shati i apologize we gotta we gotta do take a course on how to like pronounce names i don't i don't think that would help us i don't think i think it would i'm gonna whatever affliction we have when it comes to pronunciation i don't think it's curable uh at me on on twitter or github if there's a course i can take but um they wrote i believe the concept you're searching uh was inverse functions a function is invertible if it is a bijection uh in the case of scans don't consider the binary operation but instead consider the partially applied unary function so for example if you have 42 plus X, or the max of 42 X, addition is obviously

bijective, but max isn't because in this example, all values of X that are less than or equal to 42 are mapped to 42. Whereas for plus, it's not the case. So like it's a one to one mapping for a unary function. So like basically, you can think of max as like it sucks in, it maps a bunch of different values, 1, 2, 3, 4, 5, 6, 7, all the way to 42 into 42. And so because of that, you can't get back those values. But for a function like 42 plus x, whenever you have a different value of x, it's always going to produce a different answer. I'm not sure if bijection is actually what we're looking for. So I guess they're saying it's inverse functions. That being said, we also got a response

on GitHub, and this is from Roman. Explain how we got a response on GitHub. Because I said, if you don't have Twitter, just go find our... So I have... Our website is hosted using Ruby Jekyll pages,

blogs. And so it's just backed by like a GitHub repo. And so he just opened an issue or they opened an issue. Sorry. I love it. If you have any complaints about our podcast, just open an issue or send us a PR. I've decided that once every 50 episodes, which we're coming up

on now, we will quasi-reintroduce ourselves and we'll plug all our contact stuff because I don't really like plugging like, oh, you know, follow us here, blah, blah, blah. If people like it, they'll do whatever. Shouldn't we tell all the people to go leave us reviews on

the iTunes store? No. So I just said we're doing that once every 50 episodes. That's the thing. It sort of irks me when I listen to 30-plus podcasts, and they're always saying, you know, go leave a five-star review on iTunes. And I'm like, well, wait. What if I don't like your podcast enough to give a five-star review? And, like, they don't ask. They don like your podcast enough to give a five-star review? And they don't ask.

They don't ask for – some of them ask for a review. But most of them implore you to go give a five-star review. See, the podcasts I listen to are better than the podcasts you listen to because the podcasts I listen to never implore you to leave a five-star review. They just say, please leave a review. Yeah, yeah. That's the thing. I would never ask for a five-star. I would say leave the review that Yeah, yeah. That's the thing. I would never ask for five stars. I would say, leave the review

that you think is appropriate. I mean, if you don't like our content, feel, I mean, do what you want. Don't leave a review. Leave a one-star review. You know. Don't leave a one-star review on this podcast. I will find you. I see.

That's the thing is, I don't know what the typical listener looks like or what their behavior is like but I feel like if now we're gonna get a bunch of one-star reviews just I'm gonna have to wait do we have do we have reviews on iTunes I have no idea I don't I don't honestly I honestly I my my value from recording this is just getting a chat with you once every, once every couple of weeks. And then every once in a while we have people retweet or whatever, tweet at us on Twitter. I can't, I, now, but now I have to know, now I have to know.

Okay. I don't, I, I own no, I own no things from the Apple corporation. So I have no idea how to access the iTunes store, but somebody, please tell me if we have reviews, especially if they're like really bad reviews that like, just like trash us. Like, I want to know. I want to know. Oh man. If you want, if you want bad reviews, we can just go look at one of my YouTube videos. The ones where I do like the comparative languages. Oh, man.

I get a lot of hate these days. It's just like, you know, yeah. We'll save it for another episode. But, yes, we did get an issue opened by Roman Koshitsyn. Koshitsyn. Well, you know, we should tell people, you know we should tell people you know if you have if you have you know if you find some issue or you have some feedback

or something like you can open an issue but you could also like send us a PR with an audio clip of you asking the question something like that and then we can use it in the episode can they do that on a github issue uh how are they sending us i don't i'm gonna remind you of the relationship here i'm the

executive producer i come up with the big ideas you implement them so the problem is is that we deck we technically do have an email but but I already have six personal emails. I do not have the bandwidth to keep track of another email. Just have it forward to your Gmail. That's what I do. That's a lot of work. No, no, no. It's really easy to set up.

That's what I do. All right. Yeah, I'll show you how to do it. Yeah. Well, think about it. Anyways, we got to read this. We got to read this. And I've realized it actually was not not the issue was not opened by Roman.

It was opened by Sunbubble. And then Roman just posted a comment, which actually I didn't even see because it was posted seven hours ago. So very quickly, Sunbubble says, I'm pretty sure that the concept you're looking for is group. So we've got inverse functions and we've got group. A group is just a monoid with

an additional inverse operation for each element of the set. My understanding is that the inverse left scan is just a monoid with an additional inverse operation for each element of the set my understanding is that the inverse left scan is just a right scan with the inverse binary operation actually wait my understanding is that the inverse left scan is just a right scan with the inverse binary operation is that true so a a plus scan is the left scan and an inverse of that, they're saying, is a right scan with the inverse, which would be minus. So that would be that would be correct. Technically. Yeah, technically, that is, I think, correct. It's correct for the plus scan, like a plus an inverse plus scan is equivalent to a

minus right scan but is it is it correct for all the other ones sun bubble sun bubble continues to say keep in mind that both monoids and groups may or may not be commutative related to the missing reduction episode topic also as far as i know monoid or maybe strictly a semi group is the typical base property you need to be able to implement a parallel version of scans and folds. And then Sunbubble links a couple resources. And the Roman replies, I've just listened to episode 42 and found this repo to say groups, groups are everywhere, but Sunbubble beat me. Let me elaborate a bit more on this. A group is a pair of an operation and a set. This means that existence of inverse often depends not only on the operation you use,

but also on the type of elements fed into this operation. That makes sense, yeah. And then I'm not going to read through this, but Roman proceeds to say, let's show that, and then states a lemma and has a bit of a proof. At least in terms of C++, when we're talking about an operation um i think we are typically talking about a group because when we're talking about an operation we're not talking about it distinct from you know the types that it operates on like Like when we, okay, you know, sometimes we, we would talk about, you know, a subset of the inputs, like, you know, talking about std reduce on ints, but usually we're talking about like, you know, std reduce on,

you know, whether I've, we don't have a concept for the, the requirements that we put on them, but you know, that, that, that, that class of things, you know, forms a set. And, and so then when we talk about like when we talk about stood reduce, we're not just talking about stood reduce, but we're also talking about stood reduce and you know, the sequences that can be fed into stood reduce. Yeah. std reduce and you know the the sequences that can be fed into std reduce yeah looks like i gotta go after finishing this category theory book i gotta go read a set theory book i feel like set theory is actually going to be more useful than category theory if i uh if i find them i can mail you some

of my some of my math books okay and we didn't even so my my goal was to talk about the, uh, inverse functions group response and then also the other feedback that we did. And you know, I'm, I'm terrible because I knew that we, I knew that we had that inverse group, uh, uh, cause I saw it on Twitter. I knew we had that. I knew we had it to talk about, but I had to do my ranchy spiel thing. Well, no, so I was going to, I was going to say that was going to be the first episode. And then then the second one was gonna be delving into the world of combinator birds because i've just been going on a combinator tear because i'm reading to to mock a mockingbird and like it used to just be about the starlings and the phoenix and the bluebirds but now we got bald eagles golden eagles we got them all man and uh i'm catching them all and it's it's it's so awesome and it's

really it's gonna be the future. I don't understand how Haskell Curry spent, you know, three to four decades studying and writing his texts on combinatory logic. And then it just seems like the world's forgotten about it. Like everybody knows about lambda calculus. But what happened to the SKI combinator calculus? That's where it's at. That's where it's at, man. And Martin, or not Martin, Raymond Smullyan, he wrote the book with the birds.

It's more fun. Who doesn't want to learn the bird names? Who doesn't want to learn the bird names, Bryce? I put it to the listener. Don't you want to learn about the birds? We got warblers. We got cardinals. We got golden eagles now.

I do love birds and waterfowl. Yeah. Oh, my goodness. That's correct. That's correct. Bryce, I wasn't even thinking about that. I took a sign about when I was in Regina visiting a friend in August because they had a waterfowl park. And I thought Bryce, this is Bryce. That's actually not Bryce's kind of city because it's really no offense to the people of Regina.

Look, I will. Bryce is usually the one offending people of the world, but I will take a turn. Regina is not a lot going on. I think the I think the lake in the middle of the city like they made that lake. Maybe it was there, but I feel I feel like they made it. But they added a little waterfowl park next to it, and you can't run by a sign that says waterfowl park when you've got a podcast with Bryce and not think of him. And this recording has completely gone off the rails now. I guess we're going to have to do a waterfowl episode. Oh, yeah, yeah. Maybe that's what I'll call if I've decided at some point I guess we're going to have to do it. We're going to have to do a waterfowl episode. A waterfowl episode.

Maybe that's what I'll call. I've decided at some point, spoiler for the listeners, that I will come out of retirement. Spoiler for who? Spoiler for who? You said spoiler for the listeners, but there's not listeners.

There's listeners. For the listener. Thanks there's not listeners. There's listeners. Oh, yes, for the listener. Thanks for listening, listener. We really need to get back in the swing of things. This is a rough ending. This is a rough landing. Yeah, I'll say. You can fix it in post.

All right. Yeah, we should probably call it. Well, we'll wait. What was the spoiler for listener? For the listener? Oh, yeah, that I'm coming out of. I will be at some point in the future. I will come out of my speaking retirement to give a talk on waterfowl.

Okay, good. And maybe that's what I'll call it. I'll call it. Maybe I'll call it. Yeah. Bryce's birds or something I don't mind that I don't mind that at all

do you have yeah maybe that's an amazing idea that's an amazing idea were you about to ask do I have a favorite waterfowl I was but then I was thinking of actually I'm not sure geese are like geese are like you know geese are pretty good but they're also a little bit terrifying ducks are like ducks are

pretty ducks are pretty okay i'm not sure if there's any of the bird names that correspond to ducks but what would be amazing is if i didn't actually give the talk live and i i pre-recorded it as like a mini documentary where I'm explaining, getting all excited about the combinator birds. And then we cut to like a little tour of a bird sanctuary and Bryce just, oh, look, look, it's a cardinal. And then cuts to the,

a cardinal is also known as flip from Haskell and it's the C combinator. Cardinals are useful for, we cut back to Bryce. Look, it's a warbler. Perfect, perfect. It would be amazing. Although I'm not sure if we could find, I wonder if there's a bird, what do they call it? Like an aviary or a sanctuary that has all of the birds.

New York has everything. So I assume there's an aviary somewhere. Yeah, does it have all the birds, though? Does it have buntings, Picards? New York has everything. So yes, I'm sure it does. Okay. Well, wait, some of them aren't real, though.

Phoenix, that's not a real bird. No, that's not a real bird. Wait, did I click stop? Oh, no, I didn't. Okay, good. All right, I'm clicking stop now. Yes, did you? Because this is all such gold.

Such gold. We'll really be able to use this. Thanks for listening. We hope you enjoyed and have a great day.