Curried Functions - Computerphile

so a while ago we talked about the lambda calculus which is a simple but powerful mathematical theory of functions but something we didn't talk about at the time was the idea of curried functions which sound a bit spicy but are actually very useful so that's what we're going to talk about today curried functions as we often do we're going to start off with a question and the question is what actually is a function so for me a function simply takes an input on one side processes it inside and then gives an output on the right hand side so you can think of it as being a little box or a little machine takes an input on one side processes it inside the box and then produces some output on the other side so let's have a simple example of a function and as usual i'm going to be using haskell but you can basically do everything i'm going to show you today in any modern programming language that provides some support for the lambda calculus so the example i'm going to start with is a simple increment function and we define it like this increment of x is x plus one so it just adds one to a number so you can kind of have a look at the anatomy of this so the structure of this and we're doing three things we're defining a name for the function we're calling it ink for increment we're defining a name for the input parameter x and we're explaining how the output is calculated in terms of the input so we can have a couple of examples of this we could increment the number one and we get two or we could increment the number two and get three so it's all very simple and all very boring so let's move on towards curried functions now and the first step we want to take is the idea of applying a function to a function as an input so let me give you a simple example of this so what i'm going to do is i'm going to map the increment function that we just defined over the list from 1 to 10. so what map is is it's a function which takes two parameters the first parameter is another function in this case the little increment function that we just defined and the second parameter is a list of things in this case a list of numbers from one to ten and what map does is it takes the function here and applies it all the way across the list so we're just simply incrementing um all the numbers from 1 to 10. and map is called a higher order function because it takes a function as one of its inputs so let's have another example of something a bit more interesting let's think about the idea of a function which has more than one input or more than one parameter so we can define a little function called add and we're going to take two numbers x and y as inputs and then we're going to simply add them together and the important point here is that we take the two numbers x and y packaged up together as a pair at the same time okay so what we're going to do then for an example is we could add 1 and 2 and give 3 or we could add 2 and 3 and give 5. so all very simple and again all very boring as well it's not really anything uh anything new at the moment so what then is a curried function so a curried function is a function like add which takes more than one input but rather than taking them at the same time packaged as a pair or a triple or something like that it takes its inputs one at a time so how could we redefine add as a curried function what's very simple we just take the brackets out so rather than saying add of x y is x plus y in brackets we just say add of x and then a space and then a y is x plus y so it looks basically the same except we're taking the two inputs x and y one at a time now rather than at the same time in a pair and then we can apply this function in exactly the same way as before and we just give it two inputs like one and two and we get three or we can say what's two and three and we get five okay so it looks basically exactly the same as the regular addition function except rather than taking a pair of inputs at the same time it takes two inputs one at a time so then you can say well what's the point of defining functions in this curried manner well the point is that you don't need to give them all of their inputs so for example if we did add of one and we see what it says oh we actually get an error here so why do we get an error so we get an error because this is still expecting its second parameter so if i apply add to a single number one it doesn't know how to do the addition yet because we haven't given it a second number and that's what it's saying here it's trying to print a function here so it says i don't know how to show a function from integers to integers or if you want a more slightly comprehensible message it's saying maybe you haven't applied a function to enough arguments okay so with the current function which takes its input one at a time you can partially apply it to a subset of the inputs so what could you actually do with a function like add one well we could map it for example so here is a way of incrementing a list of numbers without defining a custom increment function so previously we defined ink of x as x plus one and then we mapped it here we're using the add function which is curried because it takes its inputs one at a time and all we're doing is giving the add function one parameter here and then it's a function which expects a second parameter and then it will map that all the way across the list so we get the same behavior using this general purpose addition function without having to define a custom increment function so you can ask yourself at this point what's actually going on with a current function when i say it takes its inputs one at a time what does that actually mean so let's kind of look at this definition again so here's the definition we had out of x y is x plus y what we can do is do a simple lambda calculus trick here rather than having the two inputs on the left hand side of the equals let's move them across the equal sign to the right hand side of the definition and we'll do this in two steps so what i'm going to do is i'm going to say add of x is lambda y arrow x plus y so what i've done here is the y is no longer on the left hand side of the definition here now it's on the right hand side of the definition so what this is saying is if you add a number x then what you get is a function which is waiting for a second input y and then it's going to give you back x plus y and this expression on the right hand side here is called a lambda expression it's a nameless function and it's got the same kind of anatomy as a normal function definition except for the fact that you don't give the function a name so we look at what's going on here we're taking an input parameter called y and we're giving back the result x plus y but nowhere in the blue box here have we actually given the function a name it's a nameless function and then we can actually play the same game with the other input as well so rather than having x on the left hand side we can move it across to the right hand side and here we have our definition of our add function in a more primitive way and this really lets us understand in a quite fundamental way what's going on with curried functions what we're saying is that the addition function is defined to be the function which takes an input called x and what you get back is another function and that function takes an input called y and then gives you back the result x plus y you can ask yourself where does this idea of currying come from well it's named after haskell curry who was a mathematician and logician who studied these kind of things but haskell curry himself he wasn't the person who actually invented this notation or this idea he attributes it to someone else called moses schoenfinko who was also a logician and mathematician working around the same time shown finkling is quite a hard word to say i've had to practice it quite a lot even to be able to say it today it's not it's not a word which is very easy to say whereas currying kind of just trips off the tongue it's a nice easy word to say so curry got the credit for it but really probably moses sean finkel is the one who who first studied this idea so just to wrap things up i want to give you an example which shows that actually curried functions are quite natural in the real world as well not just in computer science so if you think about a cash machine what does a cash machine do well it takes three inputs typically you put your card in you put your pin number in and you put a request in and then it's going to give you some response which usually is taking some money out and let's make this a generous cash machine let's decide that it's always just going to give you a hundred pounds or a hundred dollars out but this is not actually how cash machines work when you go up to a cash machine you don't put all of the three inputs in at exactly the same time well maybe on a saturday night when you've been out you try and put all the three inputs at the same time but this is not what happens in practice i mean you put your card in then you put your pin number in then you put your request in and finally the machine is going to give you some money out and that's because it's really a curried function so let me redefine it like that so here we're defining it as a curried function it takes us inputs one at a time so we take a card then a pin number then a request actually we can use the lambda notation to make this even more clear what's going on what we do is we take a card and we get back a function it takes a pin number and then we're going to take a request and then we're going to give back our 100 pounds so for me this definition down the bottom here really captures the essence of what a cache machine is as a curried function so it's a function that takes your card as an input and what it gives you back is a function that expects your pin number and that function takes your pin number as an input and then what you get back is a function that takes a request and finally when you get the request the machine will be very generous and just give us our hundred pounds or your hundred dollars so that's really all i want to say today about curried functions they're a very simple idea it's functions with multiple inputs that you define in a way that the inputs come one at a time rather than altogether and as i said at the start they sound a bit spicy but they're actually very simple and very useful functional programming languages take care of a lot of the implementation details that an older programming languages you have to do manually for example memory management but nowadays it's very popular to use languages like even java for example which builds memory management into the programming language functional languages do that too

Channel: Computerphile

Views: 101,438

Keywords: computers, computerphile, computer, science, University of Nottingham, Computer Science, Professor Graham Hutton, Haskell, FP, Functional Programming, Haskell Curry, Curried Functions, Lambda Calculus

Id: psmu_VAuiag

Length: 10min 17sec (617 seconds)

Published: Wed Apr 01 2020