Don and Adam Discuss Folds

Intro

Adam: This is CoRecursive. Today, we change up the format a little bit. My neighbor Don, is a software engineer. He was over last Friday for coffee, we had some super interesting conversations. I thought this would be a great fit for the podcast, so today he’s back for coffee, and he has some questions, and we recorded the whole thing. I live in a fairly generic suburban house. Don lives a street or two over, he drove over because of the super cold Canadian winter. We set up in my dining room with a couple of microphones and hit record.

Hello, sir. Come on in. Ready to podcast?

Don McKay: Yeah.

Adam: All right, let me call that the beginning.

Don McKay: All right. So first question, what is machine learning?

Adam: I do not know. I know that some machines learn, and that’s good I think?

Don McKay: I mean, according to what movie you’re watching.

Adam: Yeah. I don’t know anything about machine learning, so hopefully you brought some other questions. As much as it might be fun to hear me bumble and stumble through machine learning, I’m just going to skip forward to later in our conversation where I get to a more fun question for me to answer, which is what is corecursion, and why is the podcast called CoRecursive?

What Is Recursion?

Adam: What do you think corecursion is?

Don McKay: Recursion is a way to harness the power of repetition to get what you need. It’s a way to iterate over some sort of data until you get your ultimate goal.

Adam: Yeah, yeah. I think it’s a really good answer. The joke recursion answer is like the dictionary definition, where it’s like recursion, C recursion, and they kind of loop. But that’s actually not-

Don McKay: That’s a bad function though. I mean, come on, because that doesn’t end, right?

Adam: Yeah, so let’s say you want to add up a list, so we’re going to calculate the sum of a list of integers. So, in C we might have a while loop, we’ll have some variable, and then we’ll go through the loop and we’ll keep adding our element from the list to that, kind of mutating that state. And then at the end, we return that as our sum. The recursive way, we have a function called sum, and then how it’s going to work, is it’s going to take the first element of the list, the head of the list, and it’s going to add that to the sum of the rest of the list. And the way I’m describing it is kind of the way your implementation works. So, you take off the first element and then you add it to the sum of the rest of it, so that sum is actually recalling itself, right?

So, if you add one, two, three, you end up with one, plus two, three, which becomes one, plus two, plus three, and you get six. That is recursion, right? That’s your basic simple recursion. Where do we go from there? Another thing you could do is multiply, right? So if you have something called product, it takes a list of integers and it calculates the product. So, we’ll do the same thing. The product of a list is the first element of the list times the product of the rest of the list. And you have the same structure, where you’re always taking off the first element, and then applying something, et cetera, right?

Don McKay: Right, right.

Adam: And then you kind of need a base case for both of these to exit. For add, you can say, oh, if my list is empty, then I will return zero. So, the empty list says the sum of zero.

Don McKay: That might mess up your product though, for your product function.

Adam: So the interesting… Great transition. For product, you obviously can’t use zero because you hit the empty list, multiply everything times zero, you get zero, right?

Don McKay: Right.

Adam: So you need to use one for product, which forms a monoid. That might be a topic for another time.

Don McKay: I’m taking you way off the rails here.

Adam: Well also, I think we’re constantly in danger of me just saying things that are incorrect. So, if you think of these two definitions, we have the product and the sum, both of them kind of have the same structure. So they have, okay, here’s what we do for the empty case. And then for the non empty case, we have some sort of looping call. And so there was this guy named John Hughes, not the John Hughes who made Home Alone.

Don McKay: Oh, okay, I thought this was going in different direction.

Adam: But yeah, John Hughes is a computer scientist. He wrote this paper called Why Functional Programming Matters, in 1990. And actually here, I’ll pull up the paper. Here, I’m going to put you on the spot. It’s the abstract of John Hughes’s paper.

Don McKay: As software becomes more and more complex, it is more and more important to structure it well. Well-structured software is easy to write and to debug and provides a collection of modules that can be reused to reduce future programming costs. In this paper, we will show that two features of functional languages, in particular higher order functions and lazy evaluation can contribute significantly to modularity. We conclude that since modularity is the key to successful programming, functional programming offers important advantages for software development.

Adam: This paper is great, you can find it free online, and it just goes through some basic stuff about writing recursive functions. The thing you’ll notice about these two that we described is they have the base case and then the second case. What John shows in his paper is, oh hey, in a powerful programming language with higher order functions, where functions can take functions, you can just pull that out. We can take away that logic, put it into commonplace and that gives us the ability to handle this form of recursion all the time, using just something built into the standard library.

Don McKay: Right. So, a functional approach using recursion would enable us to take that piece of looping code, and anywhere you need to do that is now in a function somewhere. Is that what you’re talking about?

What Is a Fold?

Adam: What John is saying is, hey, I made this function called fold. Fold does this work for you, fold takes in two things. The first thing that it takes in is your base case, what do you do when you hit your empty list?

Don McKay: Exactly.

Adam: The second case that you have, is just the working case. So in my sum function, instead of being, just calling itself, I can just say list dot fold. Now for my base case, I want to give it one, and then for my function, I just give it the addition sign. So that’s just saying, hey, fold over my list, and put plus signs between each comma. I imagine it visually, if I have this one comma, two, comma, three, fold’s going to take out those commas and just put in plus signs. Does that make sense?

Don McKay: Yeah, that makes sense to me.

Adam: The previous part we were talking about, I would call that manual recursion. I’m manually calling myself.

Don McKay: Right, yeah.

Adam: Often when you see manual recursion, you can replace it with a fold. So instead of having to call yourself, you can just say, oh, maybe a fold should go here, and I think that’s cool. So, this concept-

Don McKay: It’s like folding steel. You keep folding the steel to make it stronger. I don’t know, I’m reaching for an analogy here.

Adam: Yeah, like where does the name fold come from? Yeah. So interestingly, if you think of the structure of the fold, these examples we’re talking about, we’re starting with a list of something, and then at the end we’re getting a single value. We’re sort of taking each value and folding them all together into each other, so that’s kind of how I think about it. But a lot of languages have folds, because they’re super useful. So, Scala has foldLeft and foldRight. Basically that’s just which direction you start from.

It also has just the fold. It also has something called reduce, which is the same as fold, except you don’t apply your base case. Haskell has foldl and foldr, that’s left and right. JavaScript and Java and Python all have reduce. And actually, to your question, I think reduce is maybe even a little bit more descriptive of how you were thinking about it.

Don McKay: Yeah. If you think about reduce in the context compared to just the regular fold.

Adam: Yeah. So Ruby calls it inject, which is a weird name. And I don’t know why, but I’m thinking maybe it has to do with what I was describing, where it’s like, if you have this one, comma two, comma three, and it’s like, oh, inject.

Don McKay: Inject another…

Adam: A thing between all of these.

Don McKay: I don’t know. The word inject means a lot of different things to me.

Adam: Yeah. Yeah, so Scala’s got fold, Haskell, fold, JavaScript, Java, Python, they all have reduce. If you want to sound really smart, so there’s a category theoretic term for this, it’s called a catamorphism.

Don McKay: Oh, okay. I’ll add that to my lexicon.

Change Making

Adam: So, less commonly used. That would be a really long function call, to list dot catamorphism plus. Okay, so that’s fold. We were trying, I guess you asked me what corecursion is. I’ll get there, I promise. Yeah, so that’s a fold. We’re taking some collection of things and we’re kind of reducing it, we’re folding it down. So, here’s a different recursive thing: have you ever worked in a retail environment?

Don McKay: I have worked in a retail environment, though disclaimer, it was very limited. I worked in a computer store for a high school co-op, and I had to work the till among other things, fixing computers and stocking shelves and things like that.

Adam: Nice. So, you’re at the computer store, somebody comes in, they buy something, they give you $20 and their change is like $1.57. How do you make change, I guess?

Don McKay: Well, how I did it is I put it into the till, and it was calculator and it figured it out.

Adam: But then how do you decide what dollars and coins to give them?

Don McKay: Oh, I see. So the tray comes out, and what do you grab?

Adam: Yeah, exactly. What do you grab?

Don McKay: Well, first you would grab a dollar, because that’s the largest denomination of what you owe them. And then I would grab two quarters and a nickel. And because we still have pennies back when I worked retail, I would give them two pennies.

Adam: Nice. You could give them change by giving them just 157 pennies, but you-

Don McKay: Yeah. I mean, I think you would be fired.

Adam: Yeah, this is going somewhere, I promise. You can express this as an algorithm. I’m going to have a function called make change, I’m going to pass into it 157, for a dollar and 57 cents, expressed in pennies. And then I want it to return the change that it should hand out. In a C program, I’m just going to loop, while there’s still change left to give find the largest denomination and then return that, and we’ll keep while looping, subtracting away as we return it. We can change this into a recursive function. Our base case is, if somebody calls the function, I would like change for $0. And you’re like, “Okay, here you go.”

Don McKay: Yeah, “Get out of my store.”

Adam: Yeah. What you actually do in your little function, is you just return an empty list. So, that’s your base case. It stands for, “Get out of my store.” Oh, god. I think I may never make it through the explanation. But besides the base case, if it’s more than 0 cents, then you just look at your denominations, and you say, okay, we have one that’s 100 for 100 pennies, and that’s less than the amount owed, so I return 100. Plus, I return the change for whatever’s left. So, that’s my recursive call. I’m saying I returned the first amount, and as long as there’s still change to give, I just call the function again. The first loop will return a dollar, the second loop will return a quarter, and then a quarter, and then a nickel, and then two pennies.

Don McKay: It’s like you’re continuously refactoring what you’re owing them.

What Is Corecursion?

Adam: Mm-hmm (affirmative), yeah. This is recursion again, we’re calling ourselves to get work done. But if you think about it, it has a different structure. Before what we were doing, is taking a list of elements and we were reducing them to a single one. Where here, we’re kind of doing the opposite. We’re being given a single value and what we’re returning is a list. So, if I give you 1.57, you return a list that’s like 100, 25, 25, 5, 1, 1, or something, right?

Don McKay: Yeah. I guess in my brain I went to, I’m reducing it until I don’t owe you any more money.

Adam: Yeah, yeah. There is a reduction, and you have that remainder, and the remainder keeps carrying on until it’s zero. But from the outside caller-

Don McKay: You’re creating a… Yeah, I see where you’re going with that.

Adam: It’s exactly the same, except it’s the opposite, if that makes any sense. So, earlier I said, hey, you can use this fold so you never have to manually do this call, where you’re calling itself. Well, you can’t actually make this change thing by sticking it into fold, because the fold is always working down, taking a list and working down to that single value. Right?

Don McKay: Right. And you need to have multiple values at the end of this.

Adam: Yeah. And we’re going to start with a single value, instead of having this list and taking the first element, we’re starting with a single value and traveling the remainder down. So, this is called corecursion.

Don McKay: Okay. I see, you finally got around to answering the question. I got it.

Adam: I got there, I got there. So, this is called corecursion, and the reason that they use the word co, comes I think from category theory. Because co is used to indicate that it’s the opposite.

Don McKay: Yeah, like sine and cosine.

Adam: Yeah, exactly like sine and cosine. So, recursion is taking these values and reducing them down, and the co is taking a single value and producing some, it’s the reverse direction at the type level, corecursion. So, we’re getting someplace.

Don McKay: All right.

Adam: You can do this same trick. The fold trick is we don’t need to manually do this call, let’s just make something, we’ll put it in our standard library. This generalization of corecursion is called unfold.

Don McKay: Makes sense.

Adam: Yeah, it’s pretty good.

Don McKay: Naming things is one of the hardest things in programming, but I think they nailed it. What I would like to know though is how many other candidates there were for the name of that function before they were like… The first guy came in and said, “Well, unfold,” and, “Well, I don’t know, maybe.” And there was probably a three hour meeting about the alternatives.

Adam: Yeah. Somebody from Ruby proposed-

Don McKay: Unject. I don’t think that’s a word.

Adam: Yeah. The fold is called a catamorphism. The term for unfold, for a corecursive function is called an anamorphism. If you look this up on Wikipedia, it says, “In computer programming, an anamorphism is a function that generates a sequence by repeated application of the function to the previous result. I think you can picture how the change-making, you apply it, and then with what’s left, you apply it, and with what’s left you-

Don McKay: Yeah. You have a make change and you just apply it. And then it goes through, comes back with the remainder, and then you apply it, you say make change again. And you just keep making change until there’s no more change to make.

Adam: Yeah, exactly. What did I explain so far? Why don’t you give me the summary? Let’s see.

Don McKay: See if I’ve been listening. Is this a test?

Adam: This is a test.

Don McKay: All right. So, what we have covered so far, is the fact that corecursion is the opposite to recursion, where you will start with a single value and end up with multiple values. Whereas in recursion, you will start with multiple values and reduce them down to one. And then we’ve just went into polymorphism and anamorphism. And I think that’s where you left off, as you explained anamorphism is where you take a function and apply it repeatedly until you get your result?

Adam: Yeah, yeah. I think it’s pretty close. So yeah, the anamorphism is just another way, it’s just unfold, it’s just another term for it. And a term for fold is a catamorphism. So, this topic is super deep.

Don McKay: Beyond the scope of one podcast?

Adam: Yeah. So it’s funny. I was on this podcast called Programmer Throwdown, I think. It was super fun, but yeah, their first question was like, “Is your podcast about recursion?” And I guess that could be possible.

Don McKay: Is that why you’re doing this podcast? You went on to Programmer Throwdown, and then you came and you’re like, “Well, I have to do one about recursion because I’ve been made a fool of on this other podcast”?

Adam: Exactly, exactly. So it is a deep topic, I couldn’t pull off making a whole podcast series out of it, but maybe somebody could. And there’s other things besides catamorphisms and anamorphisms, it goes deep. There’s combining them. And it turns out that a lot of complicated things can be expressed in terms of these topics.

Why Use Fold or Unfold?

Don McKay: So yeah, I guess going back to, I like to relate everything to practical applications. So, in day-to-day work, I’ve done this a lot when I’ve worked in C-sharp. I haven’t worked in C-sharp in a very long time, probably five years or six years or something. But when I did, for loops were kind of like what you did, if you had to loop over a collection of something, you just did a for loop. And I guess we stayed away from recursion, it was like a mysterious monster, where you only hear about the bad things. You’d hear horror stories about a recursive function that went off the rails, and had a memory leak, or looped infinitely and destroyed something. So, why would I use recursion over… What did you call it? The imperialist?

Adam: The imperialist approach, I like that.

Don McKay: The imperialist approach.

Adam: I called it the imperative but I like imperialist.

Don McKay: It’s imperialist. Yeah, so the imperative approach, I think is mainly what a lot of people are comfortable with, and these more advanced topics, definitely from my perspective, are interesting to learn about because I’m always looking to improve myself.

Adam: Yeah. I want to unpack some of that. I like this idea that a for loop is like, oh, that’s so simple and I can understand it, but recursion is this monster that can run out of control.

Don McKay: When I was in college, it was. I was new and just learning all this stuff for the first time, and recursion is hard to wrap your head around if you’re a programming student that’s just walking in, and being like, “Computers, I like them, I want to write programs,” and your first thing is a recursive function, it’s going to throw you a little bit. Where it’s more convenient to be able to see everything its doing at face value, in like a for loop. You can see, it’s easier to follow, whereas in recursive, you have to recursively process it in your brain. And I think that is hard for different types of people, right?

Adam: Yeah, yeah. So, I think it’s totally valid. Earlier when I was describing how sum works, it’s actually kind of declarative the recursive approach. Like if I try to describe the code for doing the kind of imperative for each, I’m like, “Okay, I’m going to make a var that’s like sum equals zero. And then for each, and then…” There’s just a lot going on there.

Don McKay: It’s very verbose.

Adam: Yeah. It’s very verbose and it has all these details that don’t seem entirely relevant. Like why do I even care what that variable at the beginning is called that I have to like mutate and what if something else changes it or… But like the fold some definition, it take a list and fold over it adding the elements together. When I describe it that way, that’s like almost what the code will be. If I use the reduce, which you like better, it’ll be like list dot reduce plus. You can just see that and think like, okay, in my head, all those commas become pluses.

I think it makes sense to sometimes trace it through in your head, like this cause, this cause this, but you can also just think about it definitionally. The function product, we take the first element of the list and we multiply that times the product of the rest of the list. I think once you get used to that way of kind of declaratively understanding things, it’s really nice. Once you understand kind of what fold means, then when you see the code, you’re like, “Oh, that’s easy.”

Don McKay: Exactly. Yeah, I think that’s the word I was looking for is like, it’s a pattern. And a lot of the times, if you haven’t been exposed to the pattern in the past, it can seem mysterious.

Adam: Yeah, totally.

Don McKay: So a lot of these methods are kind of like a, they’re very ambiguous to somebody who hasn’t seen the pattern before. Whereas if it’s a for loop, everyone’s seen that. You’ve seen that from the first day of like taking programming course.

Adam: And if we go back to what John was saying, we conclude that since modularity is the key to successful programming, dah, dah, dah, dah. And like, I think what he means by modularity right is we write our fold. It’s like three lines long or something and it has that standard. Here’s my base case, here’s my other thing. Once that exists somewhere, we don’t have to have that base case all over our code. We end up programming at kind of like a higher declarative level. Like you do Scala, whenever I have this kind of like pattern matching and I’m like case non and then case some, I should just use fold for that.

The other reason is just, I really like clean abstractions. There’s more to learn. Like you have to learn what a fold is and what a unfold is. But once you do, you’re able to kind of have this language where you can talk about these things. Let’s take it beyond lists. Let’s talk about tree. So let’s say we write a for loop that traverses a tree, you have elements and they each have children. You can write something that kind of traverses it, that kind of recursively walks through each element and prints them out or something or adds them up, and then you can do the same thing instead of having to have some complex code to add up all the elements in the tree, you just do like tree dot fold plus, tree dot fold product and get the same thing.

So once you have this abstraction, you can just talk about these things. Like we don’t work together now but if we did and we jumped on a Zoom call and you’re like, “I’m trying to figure out how to multiply all the elements and the tree.” I could say like, “Oh, just fold over it with the…” Maybe this isn’t an actual question that comes up.

Don McKay: I mean, probably not but I think we understand where you’re going with it.

Adam: I’ve had like several times where I just have some really ugly code. There’s just like some complicated logic that I’m working on and it has a bunch of cases and it just ends up seeming super complicated. And then you kind of look at it and maybe this is a fold or maybe this is a map and there’s these higher order functions. Maybe this is a flatMap and you start to pull it apart and I’ve had this happen where you start with this big, gnarly thing, you start reducing it. It gets simpler and simpler. And then it ends up just being like, poof. And instead of having my own function, I just call this built-in.

But I raised the poll request on some change I want to make to something. And then Adrian, who’s on my team and really has deep kind of functional programming knowledge, he’s like, “Oh, it looks good. But there’s like a couple of nitpicks I want to make.” And then he’s like, “Ah, you could change this to a fold and this could be a flatMap,” but basically he would be able to point out places where the logic that I was doing could be abstracted into some of these higher order components. I mean, what actually happens is I get kind of grumpy and I’m like, “Oh, I don’t want to change all this.” But I do. And I learned something and I learned this new concept. And then as a team, we have these higher order concepts to talk about.

Don McKay: I think all programmers kind of like enjoy that a little bit. I don’t know if it’s something that’s like common to the type of people attracted to our profession, but there’s something about taking through a factoring. There’s something about taking something that, well, it works. You need to see if there’s a better way to do it and that need or drive to improve the existing code that while it may work, you just need to see if it can be better.

And I find when I was first getting into Scala from C-sharp, that’s something that I was constantly doing because I was, “Well, Scala will work.” Like you can apply concepts in how you program in C-Sharp and you can apply them directly into Scala and it’ll work, but you’re not familiar with any of those higher order functions. And you look at code after you’ve learned some of them and you come back, you’re like, “Oh, I can change this whole thing and reduce it down to maybe even a few lines,” where it used to be like a dozen or something.

Adam: I have a strong opinion that this is useful, pragmatic thing to do, but also I just really like it.

Don McKay: If you want to give Adam a present, just give him some gnarly code and send it to him and be like, “Can you clean this up?” And that would be a present for you.

Adam: Yeah, right? Don’t actually do that. Well, maybe, but if you think of somebody’s learning functional programming and they write something as like a while loop and then like the next step, maybe they’re like, “Oh, I can do this without mutating this variable that I’m adding into by doing like a recursive function,” and it can be like, well, I can use a fold. So, now I don’t even have to write the recursion myself, it just becomes this like one-liner. When you get down to this fold, the fold’s going to work. It’s being used in other places, it’s not broken.

Don McKay: That’s the advantage of using some built-in functions to that. I put the language is, you know that they’ll probably work.

Adam: Yeah. But we had this other example at work. I’m making a request to this web server and it’s going to return to me in large amounts of binary, 100 megabytes or something, maybe more. And sometimes for certain servers that we were interacting with, it would start sending binary and then partway through sending the connection would die. So would send you like 10 megabytes and it would die. Somebody quick hacked in a fix, the server’s like underload or the other server has something where it just shuts down, it kills connections that are open for too long, who knows, but we have to deal with this. We need to get this data somehow. So there’s range headers.

When you make a request, you can actually say in the header, give me from this offset to this offset in the data. This is how-

Don McKay: It’s kind of like paging.

Adam: Yeah. Yeah. It’s also how like YouTube works. Like if you skip to the middle of the video, it just starts asking for data from that point. So we get like our 10 megs and then something dies. Then we have some complicated retry logic that says, okay, how far did we get? Let’s ask for more and then that’ll die and then we’ll ask for more. And we keep-

Don McKay: Yeah. I think a lot of moderate implementations of that kind of method you can see in almost anything that’s streaming or-

Adam: Yeah, totally. We had this kind of gnarly code to deal with that. And then somebody let’s just say it was me, but realized this is unfold. What’s happening is you have this function that takes in this request and it’s either going to return like 100 megabytes or if something dies, it’s going to have to keep requesting, but it’ll get the first 10 and then go, “Let me request the next 10. And then let me request the next 10,” until it’s kind of like your change remainder case, until we’ve actually gotten everything that it said was the length of the document.

So now instead of our like while loops, then we can just turn this into an unfold and kind of carry this through. And so this like gnarly server access and code got simpler. These concepts are everywhere and they’re super cool to me.

Don McKay: I mean, that’s a lot of people and I’m sure that people listening to your podcast will also have some kind of affinity.

Adam: Yeah. Maybe who knows. Yeah.

Don McKay: I recently implemented something similar where I needed to fetch a large data set. And you can’t just can’t do it all at once. I think we all kind of run into that where the data that you’re fetching is just too large for either the database or the processing. Like you want to be efficient. So you page it, you take it chunks at a time, so you just stream it in, in chunks. I did it with recursion though so maybe I’ll go back and see if I could do it with a fold.

Adam: Yeah. With an unfold.

Don McKay: Unfold.

Adam: Yeah. If you were going to grab the results of some page and it only showed 10 at a time, and then you had to go to the next page, you can write an unfold where it’s like grab the first page and then if it has a next link, then call with that and you keep on calling until there’s no next-

Don McKay: There’s no next link.

Adam: So the next is your remainder from the change example. It’s another example of an unfold. Happens all the time, man. I don’t know. So there’s a guy that I had on the podcast, Gabe Gonzales, he wrote a bunch of things about folds. Like he went really deep on it. He showed all kinds of things can be written in terms of folds. Once you understand the definition of these terms, you’re able to write some really concise code.

Don McKay: Right. It’s all of these languages share some of these operations, they just call them different things. Because when we’re executing systems, we’re all facing the same problems. We’re all coming to the same solutions just in different syntax.

Adam: Yeah. Do you know like what code golf is?

Don McKay: No, but seeing how I don’t like golf, I don’t know if I would like that.

Adam: The golf aspect of it is you’re trying to do it in as few characters as possible.

Don McKay: I feel like I might’ve done something similar by using some of the other types of websites out there, like HackerRank or-

Adam: The problem with code golf, I think it’s something fun that people do, but the code is, it ends up just like some horrible mess of symbols. But I think it’s an enjoyable process. What I’m talking about here, like using fold, using unfold, using some of these kind of FP concepts, I think it scratches the same itch. Because you’re like, “Oh, how can I simplify this?” But in the practical way. Like using fold is actually practical, using some series of pearls, symbols to do a complicated thing and-

Don McKay: I think that might be a topic for another podcast is at what point does brevity sacrifice clarity?

Adam: Yeah, yeah. A lot of what we’re talking about here, it’s actually more concise. But at what point is it so concise that-

Don McKay: It’s hard to understand?

Adam: Yeah, totally. I don’t know the answer. I think that if you don’t know the concepts, certainly if you don’t understand what unfold is, even if it’s shorter, you may not find it to be a more understandable solution.

Don McKay: I mean, you might have to consider the audience, so your team, for example, in all their different expertise levels, because if you have some people that are more junior and you’re trying to get them onto things, dumping them into something that you’ve refactored several times until it’s only a series of symbols and things might kind of be a little bit above there. It might scare them. They might think that that’s a monster that they want to avoid.

Adam: The more concise solution is more declarative there’s less saying what’s going on in individual steps, there’s less that can go wrong because there’s just less code. The other thing I would say it is more dense or harder to learn, but once you learn fold, that concept is not just for that piece of code that you’re learning. It’s everywhere. You can build a complicated thing to solve this individual problem or you can find this global concept. You’re going to have to learn about this global concept, but that learning you get to take with you.

Naming Things

Don McKay: Yeah. You’re going to encounter this a lot. When I learned it in college, they were teaching me to be more verbose so that it is more understandable. And they wanted everything, very like long names, they wanted everything very clear so that anybody could read it. And I think maybe that might’ve been more to the benefit of the instructors that were-

Adam: Yeah, the TA.

Don McKay: … leading everybody’s assignments. They just wanted everything to be clear but when you get into the workplace, you learn that that’s not the case and you don’t necessarily want to be verbose anymore. You want to be clear, but you want to be concise. And that was, I think, a learning experience coming out of college for sure.

Adam: And you just made me think of like a pet peeve what people would say, always use long descriptive variable name and you’d be like, “Okay, well what about that for loop where it’s like for i like, why isn’t the”-

Don McKay: The i name.

Adam: Yeah, why don’t I call it iterator or whatever. And like, well, we all know what the i means. It’s like don’t worry about the i. Okay, well here we have for i, for j, for k. Well, yeah, like i, j, k those are fine, g, h, past h like, no, don’t do that.

Don McKay: No. Then we don’t understand.

Adam: Yeah. Then somebody explained to me that there’s actually a just like a larger rule that always use descriptive names misses. Which is the length of your name should correspond to the length of its scope, which describes all these scenarios. So the reason that an i is fine in a for loop is it only exists in that little for loop. It doesn’t need a long descriptive name. Its scope is very small. You’re never going to be like, “I have this i here and I don’t know what it means.” It’s like, no it’s right there.

Don McKay: Yeah. You know what it means by the context in which it exists because that scope is so small.

Adam: Yeah.

Don McKay: Yeah. Descriptiveness is actually costing you clarity.

Adam: Okay. So what did I explain so far? Hopefully you understand what unfold is now and you might understand what it is for the rest of your life. Right?

Don McKay: I think there’s a point at which you start, at least at my age, things start leaving your brain as they enter them. So I might now know what fold and unfold do, but I’ve forgotten something. I guarantee it. I guarantee something that I did know before we started this podcast is now gone.

Adam: Okay. Well that might be a problem.

Don McKay: It is. It’s a constant problem.

Adam: But it’s probably something like to do with calm components or something horrible.

Don McKay: Maybe it’s something that’s irrelevant.

Why Name the Podcast CoRecursive?

Adam: But I can bring this all back around to the core concept you asked me at the beginning, what is co-recursion? We got that. Why is your podcast called CoRecursive? How about that?

Don McKay: That’s a good question.

Adam: Yeah. The very dumb answer is because I was reading a book, explaining some of these concepts when I decided to make a podcast and domain names are hard to find. I just put in some concept names and came up with that. So that’s kind of a throwaway answer. But an equally true answer is like, imagine that the podcast is some sort of function and it takes into it my interests, like when I started the podcast, so I was interested in whatever Scala and Rust and types and functional programming, so takes in this list. And then it has the step function, which is basically me talking to people where I just pull down one of these interests, find somebody and talk to them and I produced an episode.

If you think back to the type of the unfold, it takes in like a single thing. In this case, it’s a list of my interests. And then it just keeps on producing elements until it’s done which is in the elements for me are the various episodes. And it will probably never end because there must be a bug in the algorithm where like new things keep getting added to the interest.

Don McKay: I think in this example, like the interest is one giant element of things that you’re interested in and you keep… It’s the change, right?

Adam: Yeah.

Don McKay: It’s the change that you’re trying to make and you just keep coming out with denominations of currency, which is the podcast. It also sounds like you just came up with a name and then really tried to figure out what the explanation was.

Adam: That may also be true. Yeah. Did I answer your question? I don’t know, I think I just went on a long tangent.

Don McKay: I think you did. No, I think you did. I think I learned some things. I learned some things about fold. I might actually go back and look at some of my previous code.

Adam: You can go back and be like, “This code is all crap.”

Don McKay: It’s crap. I could fold this. I think anybody who’s ever written code goes and looks at things they wrote three months ago and they just look at it and discuss and they’re like, “I can’t believe I wrote this.”

Adam: If you haven’t done that or if you stop having that, then you’re probably not learning and progressing. Yeah, so this has been fun, I mean, keep bringing me your questions. I’ll keep going on rants and-

Don McKay: Oh, yeah I have lots of questions, so…

In Summary

Adam: Okay. I forgot the most important part. So let’s validate your learning. You came here and you were like, “What is corecursion and why do you use that name in your podcast?” So what’s the answer?

Don McKay: I think the answer is corecursion is, I wouldn’t say so much the opposite of recursion. It’s just the opposite result. So what goes in and what comes out is the opposite to what you would normally recur. So if recursion is turning one to many, the corecursion is turning many to one. And why is your podcast named corecursion? As far as I understand, it sounded cool and you liked the idea and it wasn’t taken, the domain name was available. And then you thought about it and came up with a reason.

Adam: I think that’s valid. Yeah.

Don McKay: I mean, that is completely acceptable. There’s nothing wrong with that. Not every name for everything has to be a eureka moment that somebody comes up while they’re in their kitchen or their shower or something like, “That’s the name.” You can just be like, “I think that’s cool. Domain’s available. It’s very practical.”

Adam: Yeah, that’s true. So is corecursion.

Don McKay: Corecursion is very practical.

Adam: All right.

That was the episode. Thanks to Don, Don McKay for being such a good sport. Hopefully this turned out all right and you’d like keep doing this. Maybe sometimes I’ll even bring him questions. He is an expert in many things that I know nothing about. Until next time, thank you so much for listening.