Algorithms & Combinators - Conor Hoekstra - NDC Toronto 2026

[00:00:10]Uh we will get started. So, welcome to the first ever edition of this flavor of this conference now NDC Toronto. Uh I've spoken twice before at the previous CPP North that I believe there were three of them dating back to 2022.

[00:00:29]And super happy to be speaking at this one. It's my I think third NDC conference. I spoke at the Oslo and Tech Town, which is outside of Oslo, conferences before. My name's Conor Hoekstra. If you want, you can QR code this. This will take you to these website we're about to see on the next slide. I'll leave it up here for a couple seconds, but I'm also going to show this at the end of the talk. If Oh, and I realized I didn't open up.

[00:00:58]Let's quickly do that so that we don't have to do this later.

[00:01:03]Uh array box Put that there.

[00:01:08]Put that full screen and then go back to this.

[00:01:11]So, this is going to take you to this page, which is basically my new about me page.

[00:01:20]So, I host four different podcasts. The main one is ADSP. Some of you may have heard of it. It has, if I think this works, 285 episodes. Uh every Friday, we haven't missed a week. I also have a YouTube channel that's got over 400 YouTube videos. And a plethora of other stuff. I'm an avid conference speaker.

[00:01:41]If you click on either of these links, it'll take you to a playlist. I have a bunch of websites, three of which we'll see. And yeah, so this is just if you want to follow me on any of the socials, you can go to that QR code and then they're linked cuz there's too many socials to to all the links for.

[00:01:56]I just visit visit this page. This was the old about me slide. I don't use this anymore, but I decided to put it on um this presentation because today we're going to be talking about algorithms and combinators, which I've talked about in a different series of talks. I think the next slide shows that I gave three different talks called uh algorithm intuition, uh better algorithm intuition, and the twin algorithms.

[00:02:20]Those were um given at different conferences, but the uh first one or the last one of them was given at the inaugural edition of uh C++ North. And then I gave composition intuition and composition uh intuition two. I haven't given the final talk in that trilogy, but uh this talk is going to kind of span the topics covered in both of these talks. So, one of them focuses more on algorithms, the other one focuses more on composition and combinators. And uh my path to this was I've been a C++ develop developer for more than a decade now, and uh when I was working at Amazon back in 2019, we started a uh functional lunch learning group where we were working our way through a couple different textbooks and learning Haskell. And uh C++ at the time was my favorite language. Haskell became my favorite language after that though because uh Haskell's fantastic. Uh but that was pretty brief, as you can see.

[00:03:14]It only lasted for about a year because then I discovered APL and array languages, and ever since that family of languages has been my uh uh favorite basically paradigm. And uh my favorite language within there changes from month to month, from week to week. And we're going to see a lot of that. But the point being is that I've been uh giving algorithm talks since basically 2019, and when I discovered these array languages, uh that's where I my love for combinators developed. And a lot of these talks that I give, you know, people find them entertaining, maybe a little bit educational, but a lot of the time people ask like how useful is this stuff actually? And uh hopefully by the end of this talk, you will um discover that they're actually very useful regardless of the language that you're operating in. Um you know, this is kind of a Does anybody know what movie this is from?

[00:04:02]Doctor Strange. You get a chocolate. I didn't mention I've got What is I almost trip over my bag here. I've got chocolates if you answer questions, if you ask questions, uh you get chocolates. So, it's supposed to be interactive. This is the scene from the first Doctor Strange where his astral projection is studying while he sleeps.

[00:04:17]And this is like if I could have a superhero I or a superpower, I wouldn't choose this one. But if I could have like three, I'd definitely choose this one cuz uh I need more hours in the day.

[00:04:26]Uh I would want to fly before I could study in my sleep. Uh but there's not enough hours in the day anyways. The point being is I I dream about algorithms and combinators. And the goal of this talk is uh to basically give you guys a uh tour of my mental model. Um before we do that though, uh everyone whip out their phones. And I really hope this works.

[00:04:45]Uh QR code this and it's going to take you to a page where you can choose as many as you want the languages that you program in. Oh, and it's working, folks.

[00:04:55]Uh either for your job or your hobby.

[00:04:57]Look at that animation.

[00:05:00]We're in the age of AI, folks. I said make sure those pie slices move dynamically as the votes come in.

[00:05:06]This is This is fantastic, folks. The whole talk has been a success if this works, which it does. So, we've got C++ in first place.

[00:05:15]Look at that, folks. You can see some people are They can't decide. They're you know, one person is just toggling BQN and on on and on. They're trying to uh break the vibe coded uh poll here.

[00:05:26]Uh you know, someone's can't decide whether they're programming in JavaScript.

[00:05:30]Uh but the point being here is that we've got C++ and Python at the top. So, NDC um originally, you know, the uh conferences that were in Norway, uh I don't actually know what the N officially stands for. Some people tell me that the N did stand for Norway. Some of them told me it stood for.NET. Hey, Tony's in the crowd. Just in time for my vibe coded app. This is the best part of the talk, uh Tony. This is all and also too, this isn't Slido. This is a uh cursor uh Claude 4.6 Opus um vibe coded app. There is a reverse Cloudflare tunnel running on like a terminal and uh you know, it's as beautiful, folks. Uh you know, PowerPoint's dead. This whole slide deck, not PowerPoint. It's all AI coded. Everything here, you might see some talks they say no AI was used in the making of this talk. It's all AI.

[00:06:15]100% AI. Every website you see, everything you see. I mean, the logos I collected before AI and but I did have AI put them in a repo. But anyways, Python, C++, that's fantastic cuz those are two of the languages that you're going to see in terms of um the combinator spellings later. But anyways, we got a variety of folks. APL BQ at the bottom. Uh only a little bit of Rust. Uh TypeScript, JavaScript, and C. So, unsurprising that these are in the top.

[00:06:41]All right. Moving on to the uh next slide. And and uh we are going to see that uh across this talk, we're going to see different uh instances of this site.

[00:06:51]So, this is one of the websites. I actually wrote this in ClojureScript pre-AI. So, this is a rare example these days of handcrafted code from uh uh before the time of AI. And the idea is here is you um input the name of uh an algorithm and then it's going to find you the same named algorithm across different programming languages. But then also, if you have different semantics attached to the name of an algorithm like we're going to see a couple times, you can index in and see for the semantics of C++, what are all the other algorithms under different names across different programming languages. So, it's a nifty tool if you're someone like me who's hopping between different languages and you want to know what's the equivalent of uh filter or a unique in C++ in some other esoteric language, uh this site will enable you to find that. And so, the idea is is I'm going to be talking about flavors of algorithms within algorithm families in this talk. But it doesn't matter what language, whether it's Java, C++, Python, you can find the equivalent of this flavor of algorithm. It might be under a different name, but it's it's the idea, the flavor of the algorithm, not necessarily the name.

[00:07:51]So, that brings us to a tour of my algorithm and combinator mental mental model. So, we just saw Google translate.

[00:07:56]We're going to see my combinatory logic website later. But, the first thing we're going to do is we are going to start off with an algorithm. So, this is one of my sites that I have coded. It came to into existence in January of 2026. And this is it's my best website I've ever made.

[00:08:13]And AI is basically responsible for everything.

[00:08:15]It is a online REPL for all of my favorite array languages. So, APL, BQN, Uiua, J, Cap, and Tiny Apple.

[00:08:25]This stuff basically auto updates on its own. I've got a bunch of GitHub. You heard that GitHub was failing the other day? It's because of people like me.

[00:08:30]I've got a bunch of GitHub actions that are not just checking for updates, but that are rebuilding, you know, WASM. You know, so APL is written in C, BQN C, Uiua is written in Rust, J is written in C, Cap is written in Kotlin, and Tiny Apple is written in Haskell.

[00:08:43]The whole infrastructure that I had AI built, you know, updates all this stuff.

[00:08:46]It's fantastic. And you can do a bunch of different things. So, you know, famously these languages have, you know, symbols, and they're hard to type. And so, you can see the keyboard mappings if you're someone that likes to memorize this stuff. And you can, you know, type toggle through all the different languages. We're going to primarily stick in Tiny APL for this talk. But, if you want, you can, you know, type and just type in the name. You don't actually need to memorize anything. There's a bunch of different ways to input stuff. I myself am going to be using the keyboard shortcuts.

[00:09:14]But anyways, enough about this arraybox.dev. You can check it out later if you want. So, the first algorithm we're going to look at today is an algorithm called replicate. And it comes from a family of algorithms that I consider the copy family. So, if you hit F1 next to any glyph while you're coding, it'll bring up in line in the page the docs. And uh, know, you could read this if you wanted to, but we're just going to play around with it, because that's the easiest thing to do.

[00:09:40]So, uh, it's a a binary function. Oh, yeah, and ask questions anytime. Feel free to interrupt. I saw a hand half go up, and then come back down.

[00:09:47]Yes, no? No? Okay, no. So, uh, maybe you're just stretching. Uh, it's a binary function. So, you're going to hear me say unary and binary. In today's talk, unary is shortcut for one argument function. Binary is shorthand for two argument function. So, this is a binary function, meaning it takes two arguments. And in these languages, a binary function is infix. So, you ever seen 1 + 2? That's infix. We're going to see the same thing for all binary functions in this talk. So, three, what does that do? If you had to name this algorithm, just for this instance of it, what would you call this?

[00:10:20]Replicate? Well, I've already told you that. But, in this instance, what are we doing? We're just repeating. There we go. Hopefully, you like Kit Kats. He's at the back of the room. What a throw, but a bad catch. It went straight to him, folks. What a bad catch. It wasn't a catch. But, yes, you would call this repeat. It's just repeating your argument. So, this is an instance of this algorithm, where it takes an integer argument as its left argument. But, there are, uh, different flavors of this. So, um, we can make sure we're outputting that to here. And a different flavor of this is if we give it a boolean mask, and then a string or an array of the same length.

[00:10:57]So, what do you think this is going to do?

[00:11:00]I know Max knows, but does anybody in the crowd that's not familiar with these languages?

[00:11:05]Sorry? Yes.

[00:11:07]Tony gets a Tony gets a a a chocolate.

[00:11:11]It is a version that at one point in the history of APLs was called compress.

[00:11:16]It's basically copying all of the elements that correspond to boolean ones, in other words, trues. So, you're going to see AC. It drops the B.

[00:11:27]And there is a final flavor of this, uh, algorithm, where you give it an integer mask instead of a boolean mask.

[00:11:37]So, if we give it 1 2 3, replicate, ABC, any guesses to what this will do?

[00:11:44]Yes, a chocolate right there in the second Well, that seems like a deformed chocolate, but talk to a whatever corporation makes these.

[00:11:52]And yes, it copies each element the corresponding number of times.

[00:11:58]So, you can think of the first one as a repeat, the second one as a compress, and the third one is just the actual name replicate.

[00:12:06]But, they call this the same thing. It's just replicate for all these instances.

[00:12:11]But, it's it's interesting in in my mind. I think of these all That's actually not that bad. I thought it was going to be like a building fire alarm.

[00:12:23]So, everyone just needs to hit okay on their phone.

[00:12:26]>> [laughter] >> It's just a amber alert or what do you call it? A test.

[00:12:33]All right, that's good enough. Question from Tony in the second row.

[00:12:38]What does 3 ABC do? A great question.

[00:12:41]What do you think it does?

[00:12:45]Yes.

[00:12:46]It just copies each element that number of times.

[00:12:52]And so, the point here though is that you've got an integer argument, a boolean mask argument, and then an integer mask argument. Three different types of arguments that give you what in maybe a different language would be actually three different named algorithms. In APL, we squeeze this all or in Tiny APL, we squeeze this all into one glyph. But, you've got three different things here. So, you can think of this as you know, or actually I'm not going to put the comments. We'll we'll just go to the next slide, which is this. So, in the copy family, and this is this is basically one of the two main takeaways in this talk is that think about different algorithms within a single family as having different flavors which are defined by the argument type that it takes. And you can see here at the bottom we've got the integer repeat, the boolean mask compress, and the integer mask replicate. And they all correspond to a single glyph in Pony Apple. Does anybody know though what would you name or what is the name for the unary and binary versions of this copy argument? So in the in the unary case that means what algorithm or function takes a unary predicate, a function that takes a single argument and returns you a true or false, and then does this kind of copying or replicating? Does anybody know what the most common name for that function or algorithm is? It exists in C++ it exists in Python It exists It exists in a library somewhere in Python whether it's a built-in or not. It exists in every single functional language.

[00:14:25]Boolean?

[00:14:27]Um No, but that's actually a half decent guess. There are um algorithms called I think apply or like boolean apply in libraries in Python like NumPy that are not far off from what I'm looking for.

[00:14:44]But that is not the name I'm looking for.

[00:14:49]I've heard count, I've heard four.

[00:14:53]Copy if is you're like four slides ahead of it and that was supposed to be the harder version of this question. So copy if yes, copy if It's I mean I actually had that realization two days ago when I was working on this talk because there's a much more popular name. All of you have heard of it. None of you are thinking of it.

[00:15:11]Not copy, but copy if is a version of this and I realize oh yeah, copy if takes a unary predicate, it copies the elements, You You are going to kick yourself.

[00:15:23]Filter.

[00:15:26]So, what is filter?

[00:15:30]Let's put the little copy uh family here.

[00:15:37]And we're going to make a function called uh filter.

[00:15:44]And so, what this means right now is we just have an uh identity function. Just a function omega is our argument here.

[00:15:50]And uh we are then going to uh test this with let's just say an iota five sequence. So, right now we just get zero to four. But, we want to filter odd elements or, you know, some criteria.

[00:16:03]So, in order to make this a higher order function that takes a function, we actually need to make this a higher order function, which you do with the following.

[00:16:10]And so, now you specify, you refer to your um predicate or operation that you want to filter on with this if I can type correctly.

[00:16:20]Uh backtick shift A, backtick shift A.

[00:16:22]So, this is our function. And so, for this function, we want to do um an odd function. So, this is a modulus um and then this is two.

[00:16:33]Uh two modulus. So, that's the equivalent of doing a remainder two. Um so, we're going to filter out even functions and keep the odd ones. And so, if we do this we now get a boolean mask where the ones correspond to our odd elements.

[00:16:49]And so, now using this with our replicate function if we parenthesize this mask and pass it as our left argument and then put our original argument here we've now filtered out the uh even numbers and we're left with the odd numbers.

[00:17:05]So, filter takes a unary predicate.

[00:17:07]Probably one of the most common, you know, you've heard about reduce, you've heard about uh map. Filter is always like the third one, but we don't think about these algorithms in terms of like which one takes an integer, which one takes a unary function, which one takes a binary function. That's the whole point of this talk. And this applies across all of the family of algorithms.

[00:17:24]So, we come back here, we can see that we've got filter, and I think the next slide, oh, look at that animation, folks, is is our filter function. And I mean, we we got beaten to the punch thanks to Max, and that's that almost every single language calls this filter, including C++. You can see C++ we added this in C++ 20 in the ranges library.

[00:17:44]But if we scroll down the bottom, and the way that they do this is they Look at that, we're missing an an e here. We've got a rendering problem, folks.

[00:17:53]Um And if it sorts basically by the most frequent. So, the most frequent name is at the top, and then the less frequent is at the bottom. At the very bottom, there's copy if. But if you think about what is the difference between copy if and filter, ignoring like the lazy semantics, they're identical.

[00:18:12]They both take a unary predicate, and they discard the ones that return false for that predicate.

[00:18:20]So, honestly, and like there's some people that say filter's a bad name, you know, we all agreed to use filter, so that's what we have. But some people say, "Are you filtering in or are you filtering out?"

[00:18:30]You know, it's always filter in.

[00:18:31]But copy if, arguably, is a better name for this.

[00:18:34]There's no ambiguity of, you know, what you're doing. You're always copying the ones where the predicate returns true.

[00:18:40]So, pretty fun.

[00:18:43]And I think that the next thing we're going to look at is our first combinator. So, um here we've done something that if you're an array programmer, it's a little bit irritating. Is we have needed to parenthesize something. You know, initially when we were building this out, we were just writing, you know, starting on the right and then adding things, putting things on the prefix. But in order to get this as the left argument of our replicate function, I needed to parenthesize it so that it could go on on left, and then put the replicate and then go.

[00:19:12]But really what I want to be able to do is spell this.

[00:19:16]But now the problem is is the Boolean mask that's going to do the filtering, it's over here and it needs to be on the left. That's just the way replicate is defined. But there is a combinator that exists actually in C++ and a bunch of languages. It exists exists in Haskell called flip. If you know of the Boost Hana library that Louis Dion did, there's a flip in there as well. It takes a binary function and commutes or flips the order that you pass the arguments to it.

[00:19:44]So this is what's known as the C combinator.

[00:19:47]Um and I just hit enter and it evaluated to the same thing. So if I I get rid of it and I do this, it's going to do something that we didn't want. Um and I think we go back here, it's going to take us here. So this is my combinatory logic website. It's beautiful, folks. And if we go here, we're going to click on the C combinator after I hit E. And so now I've added this feature basically where for any one of these combinators, you can, you know, cycle through these and we're looking at the C combinator here. So it has the bird name underneath cuz everybody wants to know what the name of the to maca mockingbird bird is. So the C is the cardinal. And right underneath it is something called arity notation. So to the left of the Y is the arity of the function that this combinator returns.

[00:20:31]And to the right of the Y are the arities of all of the functions it takes. So this is one of these simplest combinators. It takes a binary function and it returns you a binary function.

[00:20:42]And all that it does is it swaps the order that you're passing the arguments.

[00:20:46]And so we've got the Python and the C++ spellings using lambdas. Obviously the C++ C++ one is a little bit more verbose, but you can see that over on the right here, we're passing a lambda X and Y and then we're just applying a function F in the order Y X.

[00:21:00]So this is a super common thing, super useful. Jason.

[00:21:11]>> Uh yes, but for the purpose of the comment from the crowd, uh thank you Jason, was that you could write this more simply with a bind. Um that may be true, but I for consistency uh wanted this just to be lambdas across the board. Um and I admit that I only keep this here because I happen to have a library called blackbird um where I it's easy enough for me to copy and paste this stuff in, but um I think the reason I put the Python is because the lambda expression doesn't mean much to most people and the symbols don't mean much to anybody unless if you're in a rate programmer, but uh I've gotten a lot of feedback in past talks where I've shown like just a whole screen of all the different combinators in the Python code and they go, "Oh, like that's what you've been talking about all this time when you said B and B1 and fine and fine." Like that's just very simple. These are just like basically function manipulating functions. You give it functions and it gives you back some other function that it does. And so if we if we look at the one above, W, W is a function that takes a binary function and returns you a unary function.

[00:22:08]So if you think in your head, how could you possibly do that?

[00:22:12]The easiest or most obvious way is just to duplicate, to copy your argument twice, which is what you can see on the Python expression. We just have our binary function F and we just pass our single argument X twice.

[00:22:29]Um it could. So in combinatory The question was does this apply to n-ary functions?

[00:22:37]We have a binary function here, but could you replace the In the arity notation, could you replace two with n?

[00:22:43]And would that work? Uh in combinatory logic, I've actually haven't seen the W combinator spelled as a um kind of variadic combinator, but there are variadic combinators where we look at the phi and phi1 and B and B1, but really you can go to B2, B3, B4, B5. And there are actually some libraries. So Julia has the B combinator, but it actually is the variadic. So, if we look at B, what is B? This is the most common form of composition. So, if you've seen other C++ talks or Python talks, this one gets mentioned a lot, and they just call it compose. It's where you take a unary function and another unary function, and you get back a unary function. So, you're just calling one after the other, F after G.

[00:23:22]So, this is what when people think of function composition, this is typically what they're thinking of. But, there's also the B1.

[00:23:30]Which takes a binary function, a unary function, and returns you a binary function.

[00:23:35]So, that's applying a binary function to two arguments first, then you get back one result, and then you're calling your unary function on that result.

[00:23:45]But, you could, if you wanted to, generalize this.

[00:23:49]Cuz really, all the difference between B and B1 is that we change the arity of that first function that's being applied. So, you can go from one to two to three to four to five to six, and then that's what's called the B you know, underscore n.

[00:24:01]Um but, that only really comes up in the academic papers, because the most useful versions of this stuff happen to be the ones that take one and two argument functions.

[00:24:08]But, it's a great question.

[00:24:10]More questions before we uh we move on?

[00:24:13]All right. So, that brings us back to uh here, and we're going to click down here. And uh so, now we've got a different variant of this filter function that's now using a combinator in order to implement this. And I think if we go back here, we can actually do um you know, one better. Which is that here we're spelling our argument twice.

[00:24:35]So, we want to use it once when we're uh having the basically unary predicate applied to it, and then another time when we want to do the replicate at the end.

[00:24:44]And this happens to be a very, very common pattern. When you're basically doing a binary operation, you're passing the same argument twice, but for one of those times, you want to do some pre-processing. In this one, you're applying that unary predicate to get a a boolean mask back. And uh if we go back to the uh combinator page, um the version of this that you've heard about the most, if you've heard about this, is the S combinator. Um if you've ever heard of the SKI combinatory calculus or the SK combinatory calculus, um that's what the S is in this. It's taking a binary function and a unary function and applying the unary function to the argument. And then taking the original argument with that and passing both of those things to the binary function.

[00:25:27]So, in this case, it's applying the unary function to the right argument.

[00:25:31]But, we're actually trying to apply to the left argument because we want that boolean mask on the left. So, there is a sibling algorithm to the S combinator called the sigma combinator. Which all it does is if you look, it switches where the unary function is being applied.

[00:25:46]And it's a little confusing cuz I'm swapping F and G. But, that's that's you can ignore that. That's just due to the fact that in these languages, typically you put your binary function on either the left or right depending on where you're applying that unary function. You could technically just go binary unary and then have two different combinators, but when you have these infix things, it's nicer to spell it. Um and so that's what we want. We want the sigma combinator here. So, we can come back here and we can get rid of the W combinator. It might be hard to remember, but this double alpha underscore is our unary function. So, we put our unary function uh on the right here and then we need to put the sigma.

[00:26:22]So, this is the sigma combinator. If we do an F1 on this, it's called the left hook, but it corresponds to the sigma combinator in uh uh combinatory logic. And so, if we do this, once again, you're not going to see any change, but that's because this is the same code that we just wrote. And this is, you know, beautiful. Uh the fact that we're really just dealing in composition now here. Um we've got our unary function, our binary function, a combinator in between it, and it's fantastic. So, if we go back here and we click at the bottom, uh Uh we've now got two different spellings. One uses the C combinator, one uses the sigma combinator, but these things, when you start to understand them, they show up everywhere. Um and so now I believe this takes us to what is the binary version of this algorithm.

[00:27:05]We've seen integer, we've seen boolean mask, we've seen integer mask, we've seen unary predicate.

[00:27:10]Is there an algorithm that takes a binary predicate?

[00:27:15]And it does this kind of filtering or copying.

[00:27:21]Or actually, I think the next slide actually is pointing out what Max uh showed uh earlier. So this was supposed to be kind of like a surprise that look at that copy of set the bottom, but Max already knew. Um and then we come back to what's the binary version of this.

[00:27:38]And this one, if I was in the crowd, I might not even get because it's very tricky.

[00:27:44]The name of this that I first was looking for, I did find, but then I even thought that this actually is a C++ algorithm, just under a completely na- a name that obf- obfuscates it so much.

[00:27:57]And I I don't want to go to the next slide because I think we're just going to not transform from JSON. So we're going to we're going to leave this named filter.

[00:28:06]And let's get some random data here.

[00:28:11]Um and we're going to output this, and so we want our random data to be, we'll say, 10 values of um the value two. Or actually, let's give it four.

[00:28:23]And we're going to we're going to have to replace our unary function with the a binary function, right? So for here, we want to get rid of uh adjacent equal values. Um and uh then if we make this random, that's what our question mark is here, and then we just put this back to the beginning.

[00:28:44]Um that's what we're going to work from.

[00:28:46]And I think actually here, before we do this, we are going to have to skip to our um, map family. Um, so we we started with the copy family, and we're we're moving on to the map family. There's not a ton to say here. Uh, mapping a lot of the time is implicit in array languages.

[00:29:02]Um, we've got different names for these things in different languages. So, the most common are map and map two. Um, map and map two are in the same algorithm in C++. Does anybody know what it is?

[00:29:14]Transform.

[00:29:15]Transform it is indeed.

[00:29:18]"Only here for the chocolate." Tony says. Um, but yeah, so almost every single language calls the map map. Um, it's one of the other uh, languages that has a lot of consistency. If we scroll down here, you can see that in some languages, the array languages, they call this each.

[00:29:33]Um, but transform's at the very bottom.

[00:29:35]Very sad for C++. Um, the next one is map two. Map two is just map, but it takes two sequences. So, map takes a unary operation and applies that to a sequence. Map two takes two sequences and applies a binary operation.

[00:29:49]And that's transform in C++ because there's two different overloads in C++.

[00:29:54]There's an overload that takes a unary operation, and there's an overload that takes two ranges and a binary operation.

[00:29:59]And uh, this is uh, named um, different things in different There's less consistency. Some of these just have variadic maps. That's what the map star is. Um, others call this map two. In uh, range V3, it's called zip with, although I believe they changed it to zip transform because that's what C++ uh, 23 or 20 ended up calling it.

[00:30:19]And um, so this one, it's super common.

[00:30:23]You probably use it all the time without even thinking about it if you have access to a variadic map. Cuz in Python, uh, it doesn't even show Python there for some reason. Um, Python just has a variadic map. So, you don't even think about when you're combining two sequences. Um, and then after that, we have the least well-known of the maps, but my favorite, uh, and arguably the most important, uh, the adjacent map.

[00:30:42]Um so this, once again, not a whole lot of uniformity when it comes to naming this thing. It used to be called or still is called adjacent difference, which is what came out in C++ 98. We got a better version of that. If there's anything I contributed to C++, it would be the naming of the C++ uh 23 adjacent transform. Um and one of my big things has been that you shouldn't encode the semantics of the binary operation, that is the default binary operation that comes with an algorithm, into the name. That's what adjacent difference does. The default binary operation is subtraction.

[00:31:13]Because you're trying to get the difference between adjacent elements.

[00:31:15]But really, you can replace that binary operation with anything.

[00:31:18]Well, someone once pointed out to me, it was Ben Dean, that you can calculate Fibonacci numbers by replacing the default binary operation, minus, with addition.

[00:31:28]And so now you're calling adjacent difference plus to add adjacent elements together? Well, what are we What are we doing now?

[00:31:33]That's just That honestly looks like a code smell if you're calling an algorithm called difference and then overloading it with plus. Whereas if you if you call that with adjacent transform, well, now you're just transforming your sequence, you know?

[00:31:44]It's not a bad name.

[00:31:46]Um and uh the reason we bring up these this map family is because we're going to need this adjacent map in our array language in order to do the binary uh kind of copying or filtering or whatever we want to call that.

[00:31:59]And uh that was a a spoiler if you were able to see that. Folks on YouTube, just pause the screen and now it's ruined for them. But so there is uh there's a function uh called stencil, which is basically your adjacent map. It takes a binary operation and a single sequence and applies that binary operation to adjacent elements.

[00:32:18]So in this case, we just want to apply our function that we're passing in. So now we are checking are adjacent values equal to each other? So if you look at, you know, the input is uh array, which is the um you know, first line, and where we have a three and a three next to each other, that corresponds to the Boolean one right below it.

[00:32:38]And so now what we can do is we can turn this in. We want to negate this in order to get the mask that is going to filter things out. Or actually, I guess we want to keep it this way. And we want to add a one in order to get back the same length so we can apply this as a mask correctly.

[00:32:53]And now we want to use our replicate function with the W or the C combinator once again and our original output.

[00:33:00]And now what this is doing for now is it's keeping adjacent duplicate values. But we want to filter here. So we need to put this which is not or complement in order to remove elements that are adjacent to each other and equal. And now we can change this binary operation to whatever we want. Adjacent elements that are less than, less than equal to, uh greater than.

[00:33:23]So now that we have coded this filter function that takes a binary operation, does anybody now know the name of it?

[00:33:33]Oh, who said that? Right there.

[00:33:37]That might be the hardest question.

[00:33:39]Ooh. Ooh, a bad throw but a good catch.

[00:33:42]So, um the name I was hoping people would say is adjacent filter.

[00:33:49]Because that's what this is. And you might be thinking, well you just made that up. Did I actually make it up?

[00:33:53]It exists in range V3, the library that ranges in C++ 20 and C++ 23 is based on.

[00:34:00]Um and it actually has two different variants of this function. You note that I kind of skimmed over adding a boolean one to the beginning of that mask, which means it's always going to keep the first element. Well, do we always want to keep the first one? What if we want to keep the last one? So that's what the difference between adjacent filter and adjacent remove if are. They basically are just different in terms of which element do you do you keep the second one or do you keep the first one? And uh the point being is that this algorithm exists and if we put it here the next question was going to be, does anybody know that this algorithm exists in C++?

[00:34:31]As unique.

[00:34:33]And you might be thinking, "What? That's not what unique does."

[00:34:36]But it actually does. So, if you search a unique in Google Translate, it'll This is showing you the view of every operation that's named unique. But, C++'s semantics are different than most uniques across other languages. So, if you click on the C++ one, it now brings you to a page where it shows you all the different named functions with the same semantics. And the semantics of unique are, by default, it removes adjacent equal elements.

[00:35:02]But, once again, you can overload that binary operation with any binary operation you want.

[00:35:08]And so, is unique the best name for this? Maybe because, like the argument is, is that when you're using this operation, 90% of the time you're doing a unique. And so, why not just call it unique? I would argue, though, that that is completely obfuscated what this function is actually capable of doing.

[00:35:26]What it's really doing is removing values based on some binary operation that is applied to adjacent elements.

[00:35:32]So, in my In my opinion, adjacent filter would actually be a way better name for this. Um and I'm not sure if I had chosen a different binary operation, would you have guessed unique? Uh but I I thought that would be way too mean. So, good for you for knowing, though. Um and so, if we come back uh to our slide deck, uh this is kind of the end of the um copy family. So, we've got, you know, we started off with repeat, compress, and replicate in a single glyph. And then we ended up with, you know, two different algorithms using a unary operation or a unary predicate and a binary predicate named different things. You know, like I said, the name is not important here. What's important is the semantics attached to the flavor of the algorithm. You know, what algorithm do you get when you use a unary operation and you're trying to copy elements? What do you get when you're using a binary operation? What do you get when you're using an integer? Um and think about this kind of set. And this is not an exhaustive list of unary, binary, integer, Boolean, mask, you know, there's things based on values.

[00:36:24]This is just to start to get you thinking about this kind of algorithmic mental model.

[00:36:30]And so I think next um you know, so we've covered uh copy, we've covered map, and now we're going to move on for the last part of this talk uh to the chunk family. And this is my favorite family by far. This is a a family of algorithms that if you only been coding in C++ before C++ 20, you don't think about this category of algorithms. Uh chunk is actually a subset of a uh bigger parent family, which I call cuts.

[00:36:52]Uh cuts is borrowed from the J language, but it basically means if you know what a fold is, where you're reducing, and then there's a map where you're applying an operation to the same sequence, there's a family of algorithms called unfolds or splits or cuts, where you basically take a single sequence and you you dice it up somehow, and you end up with a sequence of sequences or a list of lists or a a list of strings or something like that. And we're going to look at a a subset of that overall split family called chunk. And we're going to start off with a Boolean mask version of this in uh tiny apple called partition.

[00:37:24]So this is not the C++ partition where you're taking a unary operation and then basically doing a predicate sort. This is something completely different. So we're going to come back here. Uh we're going to now going to change this uh copy to chunk. And we're going to start uh by looking at uh this function here. So we're going to actually solve a problem called maximum consecutive ones, uh which is basically given a sequence of zeros and ones, what's the longest run of ones? This is one of my favorite problems. I have a uh GitHub repo called top 10, and it's got 10 problems that I like to I've been thinking about for years. In fact, the first problem on that list is called rainwater.

[00:38:03]I got that problem in the first or second round of my Amazon interview back in like 2018.

[00:38:10]And that's how long I've been thinking.

[00:38:11]That's 8 years now. Uh I've still been thinking about this problem. And so if we get our our array of ones and zeros, we'll do a random 10 replicate 2. Uh and we'll just get rid of that rid of this for now. So, now we you know, you hit this over and over again, we get a random sequence of um, and so what what I actually skated over this. This is called I believe they call it deal.

[00:38:33]And what it means is given an integer, just give me any number between zero and one minus that integer.

[00:38:37]And so if I if I build up a list of a bunch of twos and then I deal on this, it's just going to give me either a zero or a one. Zero or one. Pretty nice.

[00:38:46]Um, and so if I call MCO on this array, um, it's just going to do nothing for now because I'm not doing anything. But if I call, um, this partition function with itself. So, I could type this, uh, but really why do that when I have the W combinator? What does it do here? And I guess actually I need to output, uh, the original array so you guys can see what's happening.

[00:39:07]Uh, I do that and I do that.

[00:39:10]So, now we have our original array.

[00:39:13]So, what is this doing?

[00:39:18]Basically, yeah. So, Tommy and Jason, a couple people are muttering to themselves. It is chunking or in the case of the name of this glyph, partitioning your sequence to your runs of ones and it's actually dropping the zeros.

[00:39:34]Which is exactly what we want for this problem. So, now that we have this, all we need to do I mean we can do a sum, we can do a length, it doesn't really matter. Um, I guess actually we can we can do a a length. So, if we do length on each of these and then we just do a maximum reduction after that, that's our answer.

[00:39:51]So, we can just play around with this and see that it's right. So, the point being is that this partition is an example of a chunking operation. It gives you a single sequence and you apply it with a mask and so the really the way it works is the mask is dropping everything with zeros and anything that has contiguous ones it's putting together.

[00:40:07]Um, and so this is the first of a bunch of chunking functions that we're going to look at. So, uh, next up we are going to look at Oh, I guess I would I give it away. So, now we know, we know what the integer version of this is called. Um, it's called chunks, uh, primarily. In C++, um, it was added, I believe, in C++ 23, um, with chunk. Uh, but this has existed in other languages and libraries for a long time. So, let's go and code this up. So, um, we're going to get rid of MCO, and, um, we're just going to do random numbers from 0 to 10, and we're going to have a function called chunk. So, how do we do this? So, and what is the behavior of an integer chunk? Does anybody know?

[00:40:51]I mean, you saw the name of it, so you might know, but yeah, just call it out if you you're given an integer.

[00:40:58]So, if if we have a And I guess actually we can start by doing this with just a uh iota sequence, and this needs to be So, say I want to take this iota sequence, and I want to chunk it into three.

[00:41:15]What's that going to do?

[00:41:20]So, it's a great question. Tony says, do you want each one to have three? Or so there there's a bunch of different flavors. The integer chunk could be stride, which just takes every third one. It could be the one that we're going to do, which is three at a time.

[00:41:31]And if you have a uneven number at the end, you just have a partial, um, a partial chunk.

[00:41:38]>> [laughter] >> So, yeah, there there This is called I actually have a a lightning talk that I gave at CppCon 2019 called slide, stride, and chunk, which are basically showing that there are three different flavors of the same thing. And you're given two different parameters, the chunk length, and then the like stride length. So, if those are equal to each other, you get chunk. If, uh, the uh wind the chunk length that you're copperling is just one, that's your stride. You're copying one and then striding, uh, n. And then the other one is a slide, where you're fixing the, uh, slide amount to one, but the chunk length, so you just get overlapping sequences. Um, so all of those correspond though to integer chunks.

[00:42:16]They just end up having different semantics at the end of the day. So, the way that we uh do this is we want to get the length of our sequence and then uh get an iota sequence. So, I guess actually let Yeah, let's change this back to uh random numbers.

[00:42:31]And then uh we want to find a way to build up a mask with uh a one at the beginning of every sequence that we want to chunk. And the way to do that is with a modulus with our um value that we're passing in, which is three here. And so, now you can see that the start of each chunk corresponds to a zero.

[00:42:51]So, now we just have to say, where do we have zeros?

[00:42:54]And now we have a one corresponding to this is the beginning of our chunk. And then we have another operation called partition and close that when we pass this, it will basically give us chunks where the ones are, starting at where the ones are.

[00:43:10]So, now we have our chunked array for one of our definitions of uh this.

[00:43:16]So, I believe if we if we come back here, um this will show you that we are, you know, our implementation and we've added our partition and close. So, the initial partition was chunk contiguous ones, drop the zero.

[00:43:30]Our partition and close is keep everything and start a new chunk anytime you encounter a one.

[00:43:37]And now this chunk is our integer chunk given a integer n, just give me that many at a time.

[00:43:43]And uh so, now we've done integer chunk, we've done mask boolean chunk. Does anybody know what the binary chunk might be called?

[00:43:52]And this exists in C++ 23. It exists in Haskell.

[00:44:01]Going once.

[00:44:03]Going twice.

[00:44:06]It's called many things.

[00:44:09]In C++, it's called chunk by.

[00:44:11]Um other languages call this group by, some languages call this partition.

[00:44:15]Partition is a a very uh overloaded name. It means many different things in many different languages. Um but the idea here is you are given a binary predicate, you apply that to adjacent elements, and then whenever that predicate returns false, you're going to start a new chunk.

[00:44:36]Um and so we can very quickly code this up as well. So if we comment this out for a sec, we're going to uh add a chunk by. And because this is going to take a binary predicate a function, we're going to have to make this a higher order function again. And um we can chunk by equals. So if we um so it's kind of similar to what we were doing with the adjacent remove.

[00:45:03]So we've got chunk by, and we start off with just an identity identity function. And so now what we want to do is the same thing that we did when we were coding up our adjacent filter. We want to apply our binary predicate, and we want to do that uh with our stencil. And so now it's applying that binary operation to adjacent elements once again.

[00:45:25]And uh if we once again add a one here, and I believe we have to do the not trick again, we can use this with our partition and close, and now we have chunked for contiguous uh equal elements, which is quite nice. And this is basically the same pattern that we had with our adjacent filter.

[00:45:48]The only difference is that we were using a replicate before in order to do the copying, and now we're using our partition and close in order to get the chunking, which is uh really really neat.

[00:46:00]And uh if we come back here, uh you'll see that we've added uh chunk by.

[00:46:05]And that brings us, I think, to Oh, I don't know what's actually coming up here. So, we're going to need to We'll come back here in a sec. So, the last version of this is the unary predicate version.

[00:46:17]I'll give two candies if any cuz I honestly didn't know about this one. It does exist in a few languages.

[00:46:26]Yes, or in some variants of it. So, the the comment from Tony was um for the unary version, uh it chunks them based if they return true or false um for a contiguous row of elements.

[00:46:37]But, there's a a more general version actually where it doesn't take a predicate. It just takes an operation.

[00:46:41]And some uh libraries and algorithms, they call this a a selector function or a key function. And as long as it returns the same value, it'll chunk it.

[00:46:51]And actually, the fact that I said that some of these libraries call it a a key function is a a hint. They call this chunk by key.

[00:46:58]So, apply a unary operation or predicate. Predicate is just a subset of an operation. Apply that to each of um your elements, and then based on the values that that operation returns, chunk those up. So, we're going to do that. Chunk by key.

[00:47:20]And I guess actually, we can uh Cap locks on.

[00:47:30]Chunk by And what is it wanting about now?

[00:47:35]Right, because we need a key.

[00:47:38]And I spelled that wrong.

[00:47:45]Chunk by key.

[00:47:49]Should I delete this stuff?

[00:47:54]What have I spell wrong?

[00:48:01]Oh, I don't think that should be it. So, if we wanted to do um uh on Oh, Tony was correct. There you go. Two chocolates for that cone Tony.

[00:48:14]Two chocolates. All right. Yeah.

[00:48:17]If you want to swap for the different variants, I got four different chocolates up here. So, um Oh, and actually I I needed the uh I needed the chunk by.

[00:48:27]Cuz I'm an inf- exactly. I don't know why I was uh save the day there. So, what what do I want to do here? Well, first off, I just want to apply my unary operation first.

[00:48:37]And so, now that I got that, now I can just call chunk by with equal.

[00:48:43]Except what's the problem here? It's chunking up the result of applying the predicate.

[00:48:51]So, I I can't actually I want to apply this to the original sequence. I have my my mask here, my boolean mask, but now it's applying the the chunking operation. So, I see Jason confused. So, we built up our boolean mask here.

[00:49:05]And so, I I need to use that in order to do the chunking. But if I I try and pass that to chunk by, it's going to chunk up the boolean mask. I want it to chunk up the original sequence. So, I guess I can't use chunk by here. Or can I?

[00:49:18]Enter one of the most useful combinators of all time.

[00:49:23]The psi combinator. The psi combinator, folks.

[00:49:28]Come on. There you go.

[00:49:31]And this is where you start to see the utility of this stuff. Cuz if I can't use chunk by, I'm going to have to go re-implement the same thing here. But what do I want? I want a combinator that's going to apply a unary operation to two different arguments, the same unary operation, and then apply that equal binary operation.

[00:49:46]That's exactly what psi is doing. It takes a unary operation and a binary operation, returns you a binary operation, and what's the pattern? If we highlight this, it's just applying our unary operation G to each argument.

[00:50:00]And then applying our binary operation.

[00:50:01]Well, that's exactly what we want here.

[00:50:03]If we come back here, right now we're applying the unary operation first. And that results in us chunking up our boolean sequence. What we want to do is we want to copy this, and that's how you spell the psi combinator, put this here, and what that means is it says before you check equality, apply your unary operation to each one of your arguments first.

[00:50:22]And if we do that, now we get our chunked and what it's doing here is it's it's checking the arity or the parity of these. So, it's keeping odd elements together and even elements together.

[00:50:36]And this actually is a fundamental feature of C++ range algorithms.

[00:50:43]What's one of the most common operations or algorithms that you call that takes a binary operation that sometimes you actually want to apply that binary operation to a different property.

[00:50:56]The algorithm sort.

[00:50:59]But maybe you don't want to sort your strings based on the lexicographical order, you want to sort them based on length.

[00:51:05]That's what a projection is for. You apply You give it a unary function like size, and it's going to check what the sizes are before applying the binary comparator.

[00:51:16]So, the Basically, the projections in C++ 20 ranges is just like an alternative spelling of the psi combinator.

[00:51:24]If you had a psi combinator in C++, you wouldn't need projections when it comes to algorithms like sort.

[00:51:29]But like spelling this in a lambda, you know, people would whine. They'd be like, "What's a psi combinator?"

[00:51:33]Um but in languages that provide it to you, it's extremely useful.

[00:51:38]And so, if we come back here, I think the next slide it shows you our full-blown um you know, chunk, chunk by, chunk by key, and we use the C combinator for flipping our partitioning clothes in the two implementations of chunk and chunk by, but we use the side combinator, which boy, oh boy, if you if you start to play with these languages, it comes up all the time. You you'd be shocked how many times you're trying to apply the same operation, and what do you do? You just spell it twice. You spell it twice in Python. You spell it twice in C++. In fact, I guarantee you you can go and find a bunch of C++ talks out there that define a custom binary comparator that you pass to a sort, and what is it doing? It's doing dot size dot size on your two different L like left-hand string and right-hand string.

[00:52:15]That's just a pattern. We're used to spelling things multiple times. We don't want to do that. It's just it's just a composition pattern.

[00:52:21]So, uh uh you might be thinking uh we've only got I think 5 minutes left though, so I want to get to questions, you know, what is the masked integer version? So, there's another um glyph or primitive in tiny Apple called group, and it takes an integer mask, and it groups everything that corresponds to the same integer in the same chunk. And it's kind of an out-of-order chunk, so arguably it shouldn't actually go in this family, but um you know, it is what it is. So, we covered the copy family. We covered the map family. We covered uh all the families, and you'll note that, you know, the integer and the mask boolean and uh the boolean mask and boolean the boolean mask and integer masks always always have a glyph, you know?

[00:53:01]And that's because in array languages, we live in the world of arrays. It doesn't make sense to have filters or chunk bys or chunk by keys because they expect unary predicates and binary predicates. Array languages are designed to be performance when you're given arrays. In fact, some of the fastest languages, they have ridiculous like boolean SIMD optimizations, and they're built with like SIMD compilers that generate extremely fast. My latest YouTube video showed that uh the sorting algorithm for a single problem, there was a sort algorithm, a partition algorithm, and a reduction algorithm. The BQN versions beat every single one. The sort BQN was faster than every single one of the Rust and C++ reduction ones, which are just linear runtime, because they have these like bit packed boolean SIMD uh compiler back ends. I mean, they're interpreted languages, but the code that they end up running is just amazingly fast. So, a lot of the times the idiomatic thing to do in array languages is to stick with these primitives, and you're not actually going to code up these chunk by and chunk by keys. Yes.

[00:54:09]Yeah.

[00:54:13]Yeah.

[00:54:14]Mhm.

[00:54:21]Yes.

[00:54:22]Yeah.

[00:54:23]Yeah. The The thing is so the The comment is that chunk by key is so you have to calculate basically the mask itself, whereas group is expecting a mask, so you're giving it the mask. Uh and that's incredibly correct. And in fact, group is borrowed from BQN, and BQN one of the idioms there is it has a primitive called occurrence count.

[00:54:40]So, if you get the uh or uh it's occurrence count, and then there's another one, but you combine these kind of They're primitives that are like they go together. And so, it it'll generate you the integer mask that you need in order to do this kind of group by operation. You might be thinking, "Well, how am I going to get the integer mask?"

[00:54:53]There's a primitive that gives you that, and when you combine it with group, cuz a lot of the times you want the pieces so that you can build up the different flavors of these things. You don't want just like a single primitive for everything. But, another chocolate. You got your stock piles growing, don't you?

[00:55:10]Yes. Yeah. That's a good point.

[00:55:13]Yeah. And I guess too, you can see by symbolically this just uh a squiggle underline versus an underline. So, you've got the The chunk family, the copy family, the map family. All together, like I said, it's not the tiny Apple implementations or the combinators that go with these. Think about these in terms of what are the variants. If you know an algorithm in your language and it takes a unary predicate, is there a version of that that takes a binary predicate that actually might be the one that you're using that you need to use in this case. Um and uh uh I had a little bonus, but we've only got 1 minute left. So, if you're interested, come and uh talk to me afterwards and and maybe I can show folks. Um but with that, I'll say thank you and uh I'm happy to take questions.

[00:55:58]Yes.

[00:56:06]Uh yes. So, the question was is replicate uh basically the inverse of run-length encoding?

[00:56:14]And uh yes, so you can think of replicate is half of the yeah, decode.

[00:56:20]Um Yeah, that's a great point.

[00:56:27]Other questions?

[00:56:30]Going once.

[00:56:32]Going twice. All right, we'll see you in the hallway track. I'll be here for the next days, so just come say hi and uh happy to chat.

[00:56:42]>> [applause]