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