A cool Functional Programming pattern. Do you know what to call it?

I use this pattern all the time when I'm programming, and I don't know if it has a name. It involves lifting a value into a new space, solving a problem with it, then lowering it back down.

Transcript

Hello! My name is Eric Normand. These are my thoughts on functional programming.

I wanted to talk about functional programming pattern. A coding pattern that comes up pretty often in functional programming. I think it's something that's really cool and it needs a name. Doesn't have a name. I need to come up with something but let me describe the pattern, maybe you can help me.

Let's say we need to do some calculation, some operation on a value. We're looking at this value in this calculation we're supposed to do. It just seems really tedious, really tedious to do. But if we take this value, which has a certain type, and we transform it into a new type, sometimes with that new type, the operation is so easy, right?

https://twitter.com/ericnormand/status/1019235436089233408?ref_src=twsrc%5Etfw

You do the operation on the new type. I'm going to call it a new space. You're lifting it up into a different space, that has maybe a richer format, a richer amount of information. It's a different space where the operation is much easier to do. You do the operation, and then, you lower it back down. Let me give you an example.

You had some text, and the text has new lines in it, so it's a string, and I ask you, "Can you add a semicolon to the end of every line?" Well, that can get hairy.

I mean, sure you can do a bit of magic with regexes or something, but I could make it a little bit more complicated. Add a semicolon if it has an even number of characters in the line, and a period if it has an odd number, unless the first letter is a T, then put a hyphen. I can just make it weirdly complicated.

You're working on this string. What do you do? This problem becomes really hard. You got all these lines in this string. Where do you put the hyphens? How do you count between newline characters and stuff like that? It's just the wrong structure to be working on this kind of problem.

What you do? You lift it up. You take this string and you say, "This is the wrong type for dealing it for solving this problem. I'm going to turn it into a list of strings where each string is a line. I'm going to split on new lines."

When you split on new lines, you got this new type. You're in a new space. It's actually a richer space in the context of your problem. It actually becomes an easy problem to solve.

You count up the number of letters and the characters in the line. You do the right thing. Then, once you've modified each of the lines, you just join them together with new lines. That's your lowering, turning it back into a string.

This is a very common pattern in functional programming. You're taking a thing where it's hard to solve this problem for whatever reason. It's actually complicated or there's a lot of corner cases in that data type. You lift it up to a new space, do your thing and you lower it back down. You have your answer.

Another example that I really like to give because it shows something interesting about math. If you have to calculate the average of some numbers, we all know the formula. You add up all the numbers and then you divide by the count of the numbers.

What happens if the count is zero? You have an empty list of numbers. You have this corner case of zero. It crashes your whole program if you try to do it. You have to check, is it zero? What do you even return? You can't return zero because that's not true. The average wasn't zero. They don't even have an average.

It's impossible to calculate. It's undefined. This corner case of zero, what do you do? What I like to do is to lift up the numbers into a higher space, a more interesting space. I say each of those numbers is actually an average. It's an average with count one.

An average is a ratio, which means it's got a numerator and a denominator. I store those two things. I store a tuple of a numerator and a denominator. I take each number. I just pair it with one. I've got these things that I can call that each of them is an average.

Notice, if I have a pair of numbers like this, I'm never going to have a zero with any of these numbers. I never have this corner case. I can always, not with these, if I lift them, I can always lower them back by dividing, just divide the two numbers. That's my lowering operation. It's got too much wind over here.

OK. I have also a representation for this zero case. I can say there's no mathematical problem with representing the tuple zero-zero. It doesn't hurt anything. They're both the additive identity. That's what I want. You add up the top things. You add up a bunch of normally ones for the denominator. I can put in a zero. It won't change anything.

I've got this new type, which is a richer space where I can add up these averages by adding the numerator and the denominators. Later I can divide them if I want. I've removed that corner case. I've also gotten all these great algebra properties from it because now that I'm just adding. I'm in a space where I'm only adding I'm never dividing, in addition is commutative and associative.

I'm operating in this really rich space because they're associative. I can groove them however I want. I can send them off to different people to work on to different computers distributed. They can work on them independently grouped.

However I want, I can just take the list and chop it up like this chop, chop, send off the different pieces to be averaged, to be added together. They send me back the answer. I add those all together. I've got an average of all of them.

Then, the problem is lowering because we can't really lower our zero-zero case. We might have that at the end. We might have had an empty list. We can save that for later because we actually have a marker. We have a value that represents that case where we didn't have any numbers. We've actually gained something.

We do have to remember that we have that sentinel value that do not lower this one. We're not representing the lack of average with a zero or something like that, like we were trying to before.

We've gained something. It's a cool pattern. The same thing, we're lifting it up to a richer space, doing an operation, and lowering it back down. I don't know what this pattern should be called, lift-and-lower? I don't know.

[pause]

Eric: Anyway, I think that this is a pattern we need a name for. It's something that we do a lot. I want to talk one last thing about what do we need to do this pattern. Obviously, we need to identify the richer space, somehow. We also need the lift-and-lower, which are inverse property, or inverse operations of each other.

That is not always possible. Here's another example. I started to think of some good examples that are on a different domain — parsing and unparsing — similar to the text we had before.

Let's say you have some JSON. You can parse it into your language, operate on it. Pull stuff out of the hash maps, take stuff out of it, erase, count stuff up. Change it, and you can lower it back down into a string. Now you can store it somewhere on a disc, or you can send it over the wire. That's where it was before.

This string you parsed it. You lifted it up to this richer representation. You do your thing, and you unparse it. You serialize it back down to JSON, and you're good. We do this all the time. We just often don't think of it as this pattern, this lift-and-lower pattern. We need that lift-and-lower and they need to be inverses of each other.

This is a strict requirement of this pattern. Identifying that richer space is not always easy. Like with the averages, I couldn't do that when I was a beginner programmer. That was not the way I was thinking. I do have to say if you start looking for this patterns, you start looking for this richer space. Just ask yourself the question.

You're looking at a problem. It's hard. In what data type, what structure will this problem be easy? Would it be easy if I already have the same split-up on lines? I think so. That much more closely resembles the problem that you're doing. This models the structure of the problem. Keep that in your mind, that question. It's happened all the time.

When you're having trouble, just think, is there a representation where this is easier, where this is trivial even? Is there a representation where this is a trivial problem? The representation I have, can I make it turn into the representation I want? Can I go the opposite direction? If it's low C, you can't do this pattern, you can't generate the lower. What would be low C?

https://twitter.com/ericnormand/status/1050824116964642816?ref_src=twsrc%5Etfw

[pause]

Eric: If I needed to know the link of the lines, I could do some function that counted characters between new lines, and gave me a list of the counts of the line, the links of the lines. But I've lost all the characters. I only have numbers of counts of lines. Although it might be easy to know which lines to add a semicolon to, because of the counts, I can't go back.

I've thrown away information. What you're looking for is a thing that has more information, store more information. I see this often in Clojure where people get a loop going. "How do I know? How do I keep track of this thing and this other thing?" They're used to having mutable variables that they just modify throughout the loop.

What if I just bundle it all together? Just, put in there, put it in the value. Keep it all together. That's the thing that's going through the loop each time. What you notice is...this is one of John Hughes's principles — John Hughes, one of the creators of Haskell, also the creator of QuickCheck, the original Haskell QuickCheck and the Erlang QuickCheck.

John Hughes, one of the great living functional programmers in the world, at least on the academic side, he talks about using whole values. He speaks about it a little bit mysteriously, like what you mean by whole values.

This is what he means. He means, instead of having four mutable variables that you're modifying, this iteration through the loop, we're going to change this one. Then we're going to look at this one, that changes that one. You're doing all these manipulations. You get the answer. I'm not going to be snobby about it. You get the answer.

When you're moving into functional programming, you start to look at, "Why don't I keep all of these together in a single value, then have operations which modify them in well-defined ways?" Hopefully, they have some kind of interesting algebraic properties. So I'm not stuck in an iterative loop.

If they're commutative or associative, I can do interesting stuff distributed. I can do a divide and conquer algorithm — much more interesting, much more distributable, much more parallelizable. That's what you're looking for, these whole values. Often, what you're doing is you're taking a value. You're lifting operation.

You lift, there's two — there's the lift and the lower. The lift operation is just adding in extra information that will be useful when you're solving the problem in your algorithm. You solve the problem. Then the lower is throwing away that extra information. That's very often what it's going to look like.

All right. This has been a lot of fun talking about this lift-and-lower pattern. It might be what it winds up being called. I think this one might actually go in my book.

I think this is a cool one. Very awesome pattern. Whenever I find it, I'm like, "Yes! This is cool." Because it chains so well. You know what I mean? It threads really well. You say, "This is the value I have. Lift it up. Do the operation. Do the calculation. Then lower it down." Right. It just chains right through.

Awesome. See you all later. Bye.