Lecture
Nowadays JavaScript is borrowing a lot of techniques from functional programming. The advantage of using functional approaches in JS is a concise implementation in just a couple lines of code and less duplication. From this follow the downsides as well — for example, in terms of readability and understanding, especially for those unfamiliar with how functional programming works.
In the previous chapter we had a problem that prevented us from composing the functions mult5 and add: mult5 takes a single parameter, while add takes two.
We can solve this problem very easily by reducing the number of inputs to one for every function.
Trust me. It's not as bad as it sounds.
We simply write our addition function to use two input parameters, but accept them one at a time. Curried functions let us do exactly that.
A curried function is a function that accepts one argument at a time.
Currying is a transformation of functions such that instead of taking arguments as f(a, b, c), they take them as f(a)(b)(c).
Currying does not call the function — it merely transforms it.
Currying (from the English currying, sometimes — curring) is the transformation of a function of many arguments into a set of functions, each of which is a function of a single argument. The possibility of such a transformation was first noted in the works of Gottlob Frege, systematically studied by Moses Schönfinkel in the 1920s, and the name comes from Haskell Curry, the developer of combinatory logic, in which reduction to functions of a single argument is fundamental.
For a function of two arguments 
, the currying operator 
performs the transformation 
— it takes an argument of type 
and returns a function of type 
. Intuitively, currying a function lets you fix one of its arguments, returning a function of the remaining arguments. Thus is a function of type 
.
Uncurrying is introduced as the inverse transformation — restoring the curried argument: for a function 
, the uncurrying operator 
performs the transformation 
; the type of the uncurrying operator is 
.
In practice, currying allows treating a function that has not yet received all of its intended arguments. The currying operator is built into some programming languages, allowing multi-argument functions to be reduced to curried form — the most characteristic examples of such languages are ML and Haskell. All languages that support closures allow curried functions to be written.
PARTIAL APPLICATION, CURRYING
Fixing some of a function's arguments produces a new function with fewer arguments.
The term "currying" has three interrelated meanings
1. Fixing the first few arguments
2. Currying f: X*Y -> Z is constructing f`: X -> (Y -> Z)
3. Applying a curried function to arguments g = f`(x) 25
a special case of partial application, in which the first several arguments of a function are fixed
add :: Integer -> Integer -> Integer add x y = x + y inc :: Integer -> Integer inc = add 1
Turning a function F over a 2-element tuple (a pair with component types X and Y) into a function over X that returns a function over Y (such a function is called the "curried" version of F)
matchesRegexpUncurried :: (String,String) -> Bool matchesRegexpUncurried = ... matchesRegexpCurried :: String -> (String -> Bool) matchesRegexpCurried pattern = matcher where matcher s = matchesRegexpUncurried (pattern,s)
Applying a curried function to arguments:
isNumber = matchesRegexpCurried ”−?[0−9]+”
In this case, the procedure isNumber is said to have been obtained by currying the procedure matchesRegexpCurried
In theoretical computer science, currying provides a way to study functions of several arguments within very simple theoretical systems, such as the lambda calculus. Within set theory, currying is a correspondence between the sets 
and 
. In category theory, currying arises from the universal property of the exponential object; in a cartesian closed category this leads to the following correspondence. There is a bijection between the set of morphisms from the binary product 
and the morphisms into the exponential 
, which is natural in 
and in 
. This statement is equivalent to saying that the product functor and the Hom functor are adjoint functors.
This is a key property of a cartesian closed category, or, more generally, a closed monoidal category. The former is fully sufficient for classical logic, while the latter is a convenient theoretical basis for quantum computation. The difference is that the cartesian product contains only information about the pair of two objects, whereas the tensor product used in the definition of a monoidal category is suited to describing entangled states.
From the standpoint of the Curry–Howard correspondence, the existence of currying functions (inhabitation of the type 
) and uncurrying functions (inhabitation of the type 
) is equivalent to the logical statement 
(the product type 
corresponds to conjunction, and the function type 
corresponds to implication). The currying and uncurrying functions are Scott-continuous.
Currying is widely used in programming languages, primarily those that support the functional programming paradigm. In some languages, functions are curried by default, meaning multi-argument functions are implemented as single-argument higher-order functions, and applying arguments to them is a sequence of partial applications.
In programming languages with first-class functions, there are usually operations curry (turning a function with signature A, B -> C into a function with signature A -> B -> C) and uncurry (performing the reverse transformation — mapping a function of signature A -> B -> C to a two-argument function of the form A, B -> C). In these cases the connection to the partial-application operation papply is transparent: curry papply = curry.
So, with their help we'll pass the first parameter into add before we compose it with mult5. Then, when mult5AfterAdd10 is called, add will receive its second parameter.
In JavaScript we can implement this idea by rewriting add:
var add = x => y => x + y;
This version of add is a function that takes one parameter right away and the second one later.
More precisely, the function add takes a single parameter, x, and returns a function that takes the next single parameter, y, which will ultimately return the result of adding x and y.
Now we can use the new add to write a working version of mult5AfterAdd10:
var compose = (f, g) => x => f(g(x)); var mult5AfterAdd10 = compose(mult5, add(10));
The compose function takes two parameters as input: f and g. It then returns a function that takes a single parameter, x, and when called, the composition of the functions f after g is carried out with the argument x.
So what did we actually do? Well, we converted our plain old add function into its curried version. This made add more flexible, since the first parameter, 10, can be passed before the function is actually executed, and the second one — when mult5AfterAdd10 is called.
At this point you're probably wondering how to rewrite the addition function for Elm. It turns out there's no need to. In Elm and other functional programming languages, all functions are automatically curried.
So the add function stays unchanged:
add x y =
x + y
And here's how mult5AfterAdd10 should have been written, going back to Part 3:
mult5AfterAdd10 =
(mult5 << add 10)
Speaking of syntax, Elm has the upper hand over imperative languages like JavaScript, since it was originally optimized for various functional programming tasks, such as currying or function composition.
Another case where currying can really shine is the refactoring process, during which you create a general-purpose version of a function with many parameters, and then use it to create a more specialized version with fewer inputs.
Let's say, for example, that we have the following functions that wrap a string in single and double brackets:
bracket str =
"{" ++ str ++ "}"doubleBracket str =
"{{" ++ str ++ "}}"
And here's how we use them:
bracketedJoe =
bracket "Joe"doubleBracketedJoe =
doubleBracket "Joe"
We can generalize bracket and doubleBracket:
generalBracket prefix str suffix =
prefix ++ str ++ suffix
But now, on every call to generalBracket, we have to pass in the brackets themselves as input values:
bracketedJoe =
generalBracket "{" "Joe" "}"doubleBracketedJoe =
generalBracket "{{" "Joe" "}}"
What we really want is to get the best of both worlds.
If we regroup the input parameters in generalBracket, we can create bracket and doubleBracket while taking advantage of the fact that functions are curried:
generalBracket prefix suffix str =
prefix ++ str ++ suffixbracket =
generalBracket "{" "}"doubleBracket =
generalBracket "{{" "}}"
Notice that by putting the static parameters first — prefix and suffix — and the changing parameter last — str — we can easily create specialized versions of generalBracket.
The order of the input parameters matters a great deal for making the most of currying.
Also notice that the functions bracket and doubleBracket are written in point-free style, meaning the argument str is only implied. Both bracket and doubleBracket are waiting for their last parameter.
Now we can use them the way we wanted to in the first place:
bracketedJoe =
bracket "Joe"doubleBracketedJoe =
doubleBracket "Joe"
Except now we're using the general currying function — generalBracket.
if some variables don't change, currying can be used in different ways - via bind, via nested functions, via arrow functions.
prints
1600 2400 3000
#include <functional> auto curry = ([] ( int x ) -> std :: function < int ( int ) > { return [ x ] ( int y ) -> int { return x + y ; }; }); int a = curry ( 4 ) ( 5 ) // 9 auto curry_4 = curry ( 4 ) int b = curry_4 ( 5 ) // 9
Func < int , Func < int , int >> curry = ( x => ( y => x + y )); curry ( 4 ) ( 5 ) // 9
Curry = fun ( A ) -> fun ( B ) -> A + B end end . ( Curry ( 3 )) ( 4 ). % => 7
let add a b = a + b // 'a ->' a -> 'a let addOne = add 1 //' a -> 'a let x = addOne 10 // 11
( Defun curry ( x ) ( lambda ( y ) ( + x y ))) (( curry 2 ) 3 ) ; returns 5 ; due to semantic differences it returns an error (unlike Scheme) ... ( funcall ( curry 2 ) 3 ) ; returns 5
curry x = ( \ y -> x + y ) - can also be written curry = (+) curry 2 3 - returns 5
! curry - turn a binary function into a function producing a function . ! ( Named after Haskell B . Curry ) ! e . g . curry f x y = f ( x , y ) dec curry : ( alpha # beta -> gamma ) -> alpha -> beta -> gamma ; --- curry f <= lambda x => lambda y => f (x, y) curry ( + ) 1 ; >> lambda y => 1 + y : num -> num ( curry ( + ) 1 ) 2 ; >> 3 : num
function curry ( x ) {
return function ( y ) {
return x + y ;
}
}
Curry ( 4 ) ( 5 ) // returns 9
Starting with ECMAScript 5, this code is possible:
const curry = ( fn , x ) => ( y ) => fn ( x , y ) const add = ( x , y ) => x + y ; curry ( add , 4 ) ( 5 ) // returns 9
; definition ( define ( curry x ) ( lambda ( y ) ( + x y ))) ; call ( let (( curr ( curry 4 ))) ( curr 5 )) , result 9 ; or like this (( curry 4 ) 5 )
let curry x = function y -> x + y ;; (* Val curry: int -> int -> int = <fun> *) let a = curry 4 5 ;; (* -: int = 9 *)
OCaml is a language of the ML family; in languages of this family, converting a multi-argument function into curried form happens automatically:
let curry x y = x + y ;; (* Val curry: int -> int -> int = <fun> *) let a = curry 4 ;; (* Val a: int -> int = <fun> *) a 5 ;; (* -: int = 9 *)
curry = lambda fn , x : lambda y : fn ( x , y ) add = lambda x , y : x + y curry ( add , 4 ) ( 5 ) # => 9
sub curry { my $ x = shift ; return sub { return $ x + shift } } curry ( 4 ) -> ( 5 ) # 9
Starting with PHP 5.3, which added closures .
function curry ( $ x ) { return function ( $ y ) use ( $ x ) { return $ x + $ y ; }; } $ A = curry ( 5 ) $ b = $ a ( 10 ) // 15
def curry ( x ) Proc . new { | y | x + y } end curry ( 1 ) . call ( 2 ) # => 3
def curry ( x : Int ) ( y : Int ) = x + y // curry: (Int) (Int) Int f = curry ( 4 ) _ f ( 5 ) // Int = 9
An example implementation using blocks:
typedef int ( ^ Add ) ( int y ) Add curry ( int x ) { return Block_copy ( ^ ( int y ) { return x + y ; }); } Int res = curry ( 5 ) ( 6 ) NSLog ( @ "% i" , res ); >> 11
package main
func main () {
curry = func ( x int ) func ( int ) int {
return func ( y int ) int {
return x + y
}
}
print ( curry ( 2 ) ( 3 )) // 5
}
curry = @ ( x ) @ ( y ) x + y ; a = curry ( 5 ) disp ( a ( 6 )); % 11
F = {( Y ) = {( X ) =X + Y }} write ( F ( 2 ) ( 3 )), % 5
t ( A , B ): - A > B , !. call ( call ( t , 3 ), 0 ). % true
Closures and currying tie data and functions together in a way similar to objects
Memoization is a technique that implements the storage of function execution results in order to avoid repeated computations. The idea is quite simple - before each function call, a check is made whether the function was already called with the same arguments before. If it was, the stored result is returned; otherwise, the answer is computed. The result obtained is then stored and returned.
Memoization — in programming, storing the results of function execution to prevent repeated computations. It is one of the optimization techniques used to increase the execution speed of computer programs. Before a function is called, it is checked whether the function has already been called before:
Memoization can be used not only to increase the speed of a program. For example, it is used in simple mutually recursive top-down parsing in the generalized top-down parsing algorithm.
Despite its connection to caching, memoization is a special kind of optimization, distinct from caching methods such as buffering and page replacement.
In logic programming languages, memoization is known as "tabling."
A generic function for creating a memoized function is quite simple:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
function memo(fn) {
const cache = {};
const slice = Array.prototype.slice;
return function () {
const args = slice.call(arguments);
const key = JSON.stringify(args);
if (cache[key]) {
return cache[key];
}
const result = fn.apply(null, args);
cache[key] = result;
return result;
};
}
|
Where can this be used? For instance, in cases where we need to perform complex, lengthy, and/or repeated computations.
Let's take a look at three standard functions used in functional programming languages.
But first, let's take a look at the following JavaScript code:
for (var i = 0; i < something.length; ++i) {
// do stuff
}
This code has one significant harmful trait. And it's not a bug. The problem is that it's boilerplate code — that is, code that gets used over and over again.
If you write in an imperative language like Java, C#, JavaScript, PHP, Python, and so on, you'll find this pattern repeating more than any other.
That's exactly what's wrong with this code.
So let's get rid of it. Let's wrap it in a function (or several functions) and never write a for loop again. Well, almost never — at least until we've fully switched over to functional programming.
var things = [1, 2, 3, 4];
for (var i = 0; i < things.length; ++i) {
things[i] = things[i] * 10; // WARNING: MUTATING DATA !!!!
}
console.log(things); // [10, 20, 30, 40]
Well, damn! Mutability!
Let's try again. This time we won't mutate things:
var things = [1, 2, 3, 4];
var newThings = [];for (var i = 0; i < things.length; ++i) {
newThings[i] = things[i] * 10;
}
console.log(newThings); // [10, 20, 30, 40]
Okay, so we didn't mutate things, but technically we did mutate newThings. Let's let that slide for now — after all, we're in the world of JavaScript. Once we've touched functional programming ideas, we no longer want to resort to mutability.
At this point it's important to understand how these functions work and how they help us reduce the "noise" in our code.
Let's take this code and put it into a function. We'll call our first standard function map (translator's note: the English verb "to map"), since it maps each value from the old array to a new value in the new array:
var map = (f, array) => {
var newArray = []; for (var i = 0; i < array.length; ++i) {
newArray[i] = f(array[i]);
}
return newArray;
};
Notice that the function, f, is passed in, and that lets our map function do whatever we want with each element of the array.
Now we can rewrite the previous code using map:
var things = [1, 2, 3, 4]; var newThings = map(v => v * 10, things);
"Mom, mom, look, I wrote code without a for loop!" Now it's easier to read, and therefore easier to analyze.
Well, technically, the for loop is still there, inside the map function. But now we're free from constantly repeating this boilerplate code.
Now let's write another standard function, one that filters objects in an array:
var filter = (pred, array) => {
var newArray = [];for (var i = 0; i < array.length; ++i) {
if (pred(array[i]))
newArray[newArray.length] = array[i];
}
return newArray;
};
Notice that if the predicate function, pred, returns TRUE, we keep the element, and if it returns FALSE, we discard it.
Here's how you can apply filter to filter out odd numbers:
var isOdd = x => x % 2 !== 0; var numbers = [1, 2, 3, 4, 5]; var oddNumbers = filter(isOdd, numbers); console.log(oddNumbers); // [1, 3, 5]
Using our new filter is much simpler than constantly rewriting it by hand with a for loop.
The last standard function is called reduce (translator's note: the English verb "to reduce"). It's typically used when you need to take a list and reduce it to a single value, though in reality its capabilities are much broader.
Usually, in functional languages, this function is called fold (translator's note: the English verb "to fold").
var reduce = (f, start, array) => {
var acc = start;
for (var i = 0; i < array.length; ++i)
acc = f(array[i], acc); // f() takes 2 arguments
return acc;
});
The reduce function takes a folding function, f, an initial value, start, and array.
Keep in mind that the folding function, f, takes two parameters: the current array element and the accumulator, acc. It uses these parameters to update the accumulator on every new iteration. The value of the accumulator at the last iteration is what gets returned from the function.
Here's an example that will help us understand how this works:
var add = (x, y) => x + y; var values = [1, 2, 3, 4, 5]; var sumOfValues = reduce(add, 0, values); console.log(sumOfValues); // 15
Notice that the add function takes two parameters and adds them together. Our reduce function is exactly expecting a function that takes two parameters, so they work well together.
We start with the start value, equal to zero, and step by step sum up the values of our values array. With each new iteration, the sum inside the reduce function grows. And, in the end, the accumulated value is returned as sumOfValues.
Each of these functions, map, filter, and reduce, makes it easier for us to work with arrays and frees us from the tedious repetition of boilerplate for loops.
But in functional programming they're even more valuable, since in cases that call for looping, it's difficult to get by with recursion alone. Iterative functions aren't just extremely useful. They're simply necessary.
Comments