Functional Concepts

an overview

Functional languages are currently rediscovered, due to scalability issues and multicore processors, among other things. Several functional concepts, often unfamiliar to the developer accustomed to more classical languages, are becoming widespread. Here and there, you see more and more references to lambda, closure, or even partials or currying.

This article purpose is to rapidly present these concepts, without dealing with all their power, to allow newcomers in functional land to not be lost. May purists forgive me for shortcomings and simplifications.

Lambda

Lambdas, whose name comes from λ-calculus, are one of the theoretical foundations of functional languages. Left aside syntactic sugar, they are no more than anonymous functions.

In functional context, functions are natural values, and can be put into variables (or symbols), passed around, and returned (by higher-order functions). They are called first class values (no connection with object oriented programming, rather with trains).

One of the benefits of a lambda with respect to a “classical” function, is that it can be created on demand, in a local scope, and can be garbage collected when not in use. This aspect is useful with functional paradigms, which make heavy use of higher-order functions (composing, list manipulations with map, filter and reduce), as in events oriented programming, where a function is directly added to the event handler. In most of these cases, these functions are “one shot”, and it is therefore easier to define them as lambda.

In some languages, a lambda must be functionally pure, that is return a value only depending on the input, and have no side effects. The function application can thus always be replaced by its returned value without changing program semantic (called referential transparency). The return keyword can therefore be omitted, and the function call is considered as an expression, bringing syntactic sugar: the function can be written as a mathematic function (this aspect is true for all functions, not only lambda, in purely functional languages).

The following snippets are comparing the classical function definition with the one using lambda.

Lambda in Scheme (lambda.scm)
    1 (define (add a b) (+ a b))
    2 
    3 (define add
    4   (lambda (a b) (+ a b)))
Lambda in Python (lambda.py)
    1 def add(a,b):
    2     return a + b
    3 
    4 add = lambda a, b: a + b
Lambda in Javascript (lambda.js)
    1 function add(a,b) { return a + b;}
    2 
    3 var add = function(a,b) { return a + b; };
Lambda in O’Caml (lambda.ml)
    1 let add(a,b) = a + b;;
    2 
    3 let add = function (a,b) -> a + b;;
Lambda in Haskell (lambda.hs)
    1 add x y = x + y
    2 
    3 add2 = \x y -> x + y
Lambda in Golo (lambda.golo)
    1 function add = |a,b| { return a + b }
    2 
    3 let add2 = |a,b| -> a + b
In some functional languages, this distinction is meaningless. As an example, O’Caml’s first definition is just syntactic sugar for the second one. The same is true for Scheme and Javascript.

Usage Examples

Map

map in Scheme (lambdamap.scm)
    1 > (map (lambda (x) (* 2 x)) '(0 1 2 3 4))
    2 (0 2 4 6 8)
map in Python (lambdamap.py)
    1 >>> map(lambda x: 2*x, range(5))
    2 [0, 2, 4, 6, 8]
map in O’Caml (lambdamap.ml)
    1 # List.map (function x -> 2*x) [0;1;2;3;4];;
    2 - : int list = [0; 2; 4; 6; 8]
map in Haskell (lambdamap.hs)
    1 > map (\x -> 2*x) [0,1,2,3,4]
    2 [0,2,4,6,8]

Events

events handling in Javascript (lambdaevt.js)
    1 mybutton.addEventListener("click", function(evt){alert("hello");});
events handling in Golo (lambdaevt.golo)
    1 local function listener = |handler| -> asInterfaceInstance(ActionListener.class, handler)
    2 button: addActionListener(listener(|event| -> println("Clicked!")))

An other use of lambda is precisely closures

Closure

Formally, a closure is embedding external value references inside a function definition.

This is usually done with a higher-order function returning a function whose defining depends on given values.

Closure in Scheme (closure.scm)
    1 (define (adder a)
    2   (lambda (b) (+ a b)))
    3 
    4 (define add-two (adder 2))
    5 (display (add-two 40)) ; -> 42
    6 
    7 (let ((my-add (adder 21)))
    8      (display (my-add 21))) ; -> 42
    9 
   10 (display ((adder 18) 24)) ; -> 42
Closure in Python (closure.py)
    1 def adder(a):
    2     return lambda b: a+b
    3 
    4 addtwo = adder(2)
    5 print(addtwo(40)) # -> 42
    6 
    7 myadd = adder(21)
    8 print(myadd(21)) # -> 42
    9 
   10 print(adder(18)(24)) # -> 42
Closure in Javascript (closure.js)
    1 function adder(a) { 
    2     return function(b) {
    3         return a+b;
    4     };
    5 }
    6 
    7 var addtwo = adder(2);
    8 console.log(addtwo(40)); // -> 42
    9 
   10 var myadd = adder(21);
   11 console.log(myadd(21)); // -> 42
   12 
   13 console.log(adder(18)(24)); // -> 42
Closure in O’Caml (closure.ml)
    1 let adder a = function b -> a+b ;;
    2 
    3 let addtwo = adder 2 ;;
    4 print_int (addtwo 40) ;; (* -> 42 *)
    5 
    6 let myadd = adder 21 ;;
    7 print_int (myadd 21) ;; (* -> 42 *)
    8 
    9 print_int (adder 18 24) ;;
Closure in Haskell (closure.hs)
    1 
    2 adder a = \b -> a + b
    3 
    4 addtwo = adder 2
    5 
    6 myadd = adder 21
    7 
    8 main = do
    9     print (addtwo 40); -- -> 42
   10     print (myadd 21); -- -> 42
Closure in Golo (closure.golo)
    1 module Closure
    2 
    3 function adder = |a| {
    4     return |b| -> a + b
    5 }
    6 function main = |args| {
    7     let addtwo = adder(2)
    8     println(addtwo(40)) # -> 42
    9 
   10     let myadd = adder(21)
   11     println(myadd(21)) # -> 42
   12 }

In these examples, the a variable is closed in the anonymous function returned. A call to adder returns a newly created function, usable as any other function.

The adder function defines a functions set, parametrised by a.

Note that you don’t have to affect the returned function, it can be used directly as adder(21)(21).

In a sens, closures are a dual form of objects oriented programming, where behaviour (methods) is embedded in data structure. Here, the data (closed value) is are embedded in the behaviour. These two approaches define a family of processing units parameterized by their state. Instead of creating a new class instance, each closure call creates a new function (function factory).

It’s a way to emulate closures in OO languages: a callable (inner) class whose private attribute represents the closed value, as shown below in Python, which is functionally equivalent to the previous closure.

Emulating a closure with an object (Python) (simulclosure.py)
    1 class adder:
    2     def __init__(self, a):
    3         self._a = a
    4 
    5     def __call__(self, b):
    6         return self._a + b
    7 
    8 addtwo = adder(2)
    9 print(addtwo(40)) # -> 42

Even if lambda are often used to create closures, it’s not necessary if the language as inner functions:

Closure without lambda (closuredef.py)
    1 def adder(a):
    2     def annon(b):
    3         return a+b
    4     return annon
    5 
    6 addtwo = adder(2)
Concerning the garbage collector: creating a closure on a variable create a reference to it, in the anonymous function. As long as this function persists, the variable will not be collected, even if it’s initial scope is terminated (it’s this feature that allow the closures themselves).

Usage Example

Standard example in event-based programming to easily create series of similar handlers.

Using closure to create handlers (Javascript) (closureex.js)
    1 function displayMessage(message) { 
    2      // ...
    3 }
    4 
    5 function handleWithMessage(message) {
    6     return function(evt) { displayMessage(message); }
    7 }
    8 
    9 button1.addEventListener("click", handleWithMessage("hello"));
   10 button2.addEventListener("click", handleWithMessage("salut"));
Using closure to create handlers (Golo) (closureex.golo)
    1 function displayMessage = |message| {
    2     # ...
    3 }
    4 
    5 function handleWithMessage = |message| {
    6     return asInterfaceInstance(
    7                 ActionListener.class,
    8                 (|evt| -> displayMessage(message))
    9             )
   10 }
   11 
   12 button1: addActionListener(handleWithMessage("hello"))
   13 button2: addActionListener(handleWithMessage("salut"))

We have here a function displaying a message. We can’t use it as a handler, since a handler must take the event as single argument. The closure handleWithMessage use the message to display to create a new function usable as a handler. The message is closed in the function definition (to be strict, the closure is the returned function, not handleWithMessage which is rather a factory).

Partial Function Application

Closures lead us to partial function application.

Partial function application binds one or more arguments of a polyadic function, giving a new function with a simplified signature. This is equivalent to create a closure of an existing function on one or several of its arguments.

Partial application in Scheme (partial.scm)
    1 (define (add a b) (+ a b))
    2 
    3 (let ((add-two (lambda (b) (add 2 b))))
    4      (display (add-two 40))) ; -> 42
Partial application in Python (partial.py)
    1 def add(a, b):
    2     return a + b
    3 
    4 addtwo = lambda b: add(2, b)
    5 print(addtwo(40)) # -> 42
Partial application in Javascript (partial.js)
    1 function add(a, b) { return a + b; }
    2 
    3 var addtwo = function(b) { return add(2,b); };
    4 console.log(addtwo(40)); // -> 42
    5 
Partial application in O’Caml (partial.ml)
    1 let add a b = a+b;;
    2 
    3 let addtwo = function b -> (add 2 b);;
    4 print_int (addtwo 40);; (* -> 42 *)
Partial application in Haskell (partial.hs)
    1 
    2 add a b = a + b
    3 
    4 addtwo = \b -> add 2 b
    5 
    6 main = do
    7     print (addtwo 40) ; -- -> 42

In languages with undefined arguments number, a generic partializing function is easy to create. Otherwise, a function must be defined for every function arity, which can be tedious.

In languages with named arguments, it is possible to partialize any argument, not only positional ones. Python provides a generic function (functools.partial, which is created by hand here for demonstration), as well as Golo (:bindWith).

Partial application in Golo (partial.golo)
    1 module Partial
    2 
    3 function add = |a, b| -> a + b
    4 
    5 function add3 = |a, b, c| -> a + b + c
    6 
    7 function main = |args| {
    8     let addtwo = |b| -> add(2, b)
    9     println(addtwo(40)) # -> 42
   10 
   11     let myadd = ^add: bindTo(21)
   12     println(myadd(21)) # -> 42
   13 
   14     let superadd = ^add3: bindTo(14): bindTo(14)
   15     println(superadd(14)) # -> 42
   16 }
Generic partial in Scheme (partialgen.scm)
    1 (define (partialize f p)
    2   (lambda args
    3     (apply f (cons p args))))
    4 
    5 (define (add a b) (+ a b))
    6 (define (add3 a b c) (+ a b c))
    7 
    8 (let ((my-add (partialize add 21)))
    9   (display (my-add 21)) (display "\n")) ; -> 42
   10 
   11 (let ((super-add (partialize (partialize add3 14) 14)))
   12   (display (super-add 14)) (display "\n")) ; -> 42
Generic partial in Python (partialgen.py)
    1 def partialize(f, p):
    2     return lambda *args: f(p, *args)
    3 
    4 def add(a, b):
    5     return a + b
    6 
    7 def add3(a, b, c):
    8     return a + b + c
    9 
   10 myadd = partialize(add, 21)
   11 print(myadd(21)) # -> 42
   12 
   13 superadd = partialize(partialize(add3, 14), 14)
   14 print(superadd(14)) # -> 42
Generic partial in Javascript (partialgen.js)
    1 function partialize(f, p) {
    2     return function() {
    3         return f.apply(null,
    4                     [p].concat(Array.prototype.slice.call(arguments))); };
    5 }
    6 
    7 function add(a, b) { return a + b; }
    8 function add3(a, b, c) { return a + b + c; }
    9 
   10 var myadd = partialize(add, 21);
   11 console.log(myadd(21)); // -> 42
   12 
   13 var superadd = partialize(partialize(add3, 14), 14);
   14 console.log(superadd(14)); // -> 42
Generic partial in O’Caml (partialgen.ml)
    1 let partial2 f a = function b -> (f a b);;
    2 
    3 let add a b = a + b;;
    4 
    5 let myadd = partial2 add 21;;
    6 print_int (myadd 21) ;; (* -> 42 *)
Generic partial in Haskell (partialgen.hs)
    1 
    2 partial2 f a = \b -> (f a b)
    3 
    4 add a b = a + b
    5 
    6 myadd = partial2 add 21
    7 
    8 main = do
    9     print (myadd 21); -- -> 42

Those used to functional programming can note that to partialize easily a function, one can reduce the arguments list with the partializing function. In Python for example, one can write superadd = reduce(partialize, [14,14], add3).

I’ll write more extensively about reduce, as well as map as seen above (map, reduce, reminds you something?), in another article.

Currying

The above Caml (and Haskell) example is a purely didactic one, since this language allow to directly partialize any function. Calling it with less arguments as needed automatically returns a partial function.

Automatic partial application in O’Caml: auto-currying (curry.ml)
    1 let add a b = a + b ;;
    2 let add3 a b c = a + b + c ;;
    3 
    4 let addtwo = add 2 ;;
    5 let myadd = add 21 ;;
    6 
    7 addtwo 40 ;; (* -> 42 *)
    8 print_int (myadd 21) ;; (* -> 42 *)
    9 
   10 let superadd  = add3 14 14 ;;
   11 print_int (superadd 14) ;;
   12 
   13 let mysuperadd = (+) 20 ;;
   14 print_int (mysuperadd 22) ;; (* -> 42 *)
Automatic partial application in Haskell: auto-currying (curry.hs)
    1 add a b = a + b
    2 add3 a b c = a + b + c
    3 
    4 addtwo = add 2
    5 myadd = add 21
    6 
    7 superadd  = add3 14 14
    8 
    9 mysuperadd = (+) 20
   10 
   11 main = do
   12     print (addtwo 40); -- -> 42
   13     print (myadd 21); -- -> 42
   14     print (superadd 14); -- -> 42
   15     print (mysuperadd 22); -- -> 42

Since addition is just an infix function, this can be even easier as in the last snippets.

In Caml, as in other ML languages, Haskell, and others, functions are auto-curryfied. That is, a function with several arguments is actually a function with a single argument, that returns a function with a single argument, and so on. As an example, the addition signature is add : int → int → int, which can be written add : int → (int → int) (that is a function on integer returning a function on integer returning an integer).

Curryfying a function (from the mathematician Haskell Curry, who also named the functional language), means transforming it in a chain of single argument functions, or simply making it automatically partialing.

Simple currying in Python (curry.py)
    1 def add(a):
    2     return lambda b: a + b
    3 
    4 print(add(21)(21)) # -> 42
    5 
    6 myadd = add(21)
    7 print(myadd(21)) # -> 42
Simple currying in Javascript (curry.js)
    1 function add(a) { return function(b) { return a+b; } }
    2 
    3 add(21)(21); // -> 42
    4 
    5 var myadd = add(21);
    6 myadd(21); //-> 42
Simple currying in Golo (curry.golo)
    1 module Curry
    2 
    3 function add = |a| {
    4     return |b| -> a + b
    5 }
    6 
    7 function main = |args| {
    8     let myadd = add(21)
    9     println(myadd(21))
   10 
   11     #println(add(21)(21))
   12 }
Simple currying in Scheme (curry.scm)
    1 (define (add a)
    2     (lambda (b) (+ a b)))
    3 
    4 (display ((add 21) 21)) ; -> 42
    5 
    6 (let ((my-add (add 21)))
    7      (display (my-add 21))) ; -> 42

This is the same as defining the function as a chain of lambda, each one being a closure on the previous one’s argument.

Explicit currying in O’Caml (curry2.ml)
    1 let add3 = function a -> function b -> function c -> a+b+c ;;
    2 add3 14 14 14 ;;(* -> 42 *)
    3 
    4 let add1 = add3 14 14 ;;
    5 add1 14 ;;(* -> 42 *)
    6 
    7 let add2 = add3 14 ;;
    8 add2 14 14 ;; (* -> 42 *)
Explicit currying in Haskell (curry2.hs)
    1 add3 = \a -> \b -> \c -> a+b+c
    2 
    3 add1 = add3 14 14
    4 
    5 add2 = add3 14
    6 
    7 main = do
    8     print (add3 14 14 14); -- -> 42
    9     print (add2 14 14); -- -> 42
   10     print (add1 14); -- -> 42
Explicit currying in Scheme (curry2.scm)
    1 (define add3
    2   (lambda (a)
    3     (lambda (b)
    4       (lambda (c) (+ a b c)))))
    5 
    6 (display (((add3 14) 14) 14) ) ; -> 42
    7 
    8 (let ((add1 ((add3 14) 14)))
    9      (display (add1 14))) ; -> 42
   10 
   11 (let ((add2 (add3 14)))
   12      (display ((add2 14) 14))) ; -> 42
Explicit currying in Python (curry2.py)
    1 add3 = lambda a: lambda b: lambda c: a+b+c
    2 print(add3(14)(14)(14)) # -> 42
    3 
    4 add1 = add3(14)(14)
    5 print(add1(14)) # -> 42
    6 
    7 add2 = add3(14)
    8 print(add2(14)(14)) # -> 42
Explicit currying in Javascript (curry2.js)
    1 var add3 = function(a) {
    2                 return function(b) {
    3                     return function (c) {
    4                         return a+b+c;
    5                     }
    6                 }
    7             }
    8 add3(14)(14)(14); // -> 42
    9 
   10 var add1 = add3(14)(14);
   11 add1(14); // -> 42
   12 
   13 var add2 = add3(14);
   14 add2(14)(14) // -> 42
Explicit currying in Golo (curry2.golo)
    1 module Curry2
    2 
    3 function add2 = |a| -> |b| -> a+b
    4 
    5 function main = |args| {
    6 
    7     let add1 = add2(21)
    8     println(add1(21)) # -> 42
    9 
   10 }

Therefore, it is no more required to partialize these functions, since calling them with too few arguments will return a partially applied function.

Again, it is easy to write an auto-currying function, that is a function taking a function as argument and returning a curryfied version of it (left as an exercise).

To conclude

I hope these concepts are now clearer to you. If you have remarks or questions, do not hesitate to ask me.

I’ll probably continue to improve this article, specially by adding more snippets in other languages; I like such comparisons, that helps to show concepts beyond syntax and language specificities.

I made a to this article, dealing with simulating these concepts in Java.

References

If you mind explore a little more these languages:

Updates

  • : initial post
  • : Golo snippets
  • :
    • some remarks;
    • partial section modification;
    • references added;
    • Scheme snippets;
  • : English translation
  • : add Haskell snippets
  • : add links to APIHour slides