Functional Programming Concepts Glossary

Arity

The number of arguments a function takes. From the words unary, binary, ternary, and so on. This is an unusual word because it's made up of two suffixes: "-ary" and "-ity." Addition, for example, takes two arguments, so it's a binary function, or a function with an arity of two. Such a function may sometimes be referred to as "dyadic" by people who prefer Greek roots to Latin. A function that takes a variable number of arguments is called variadic. A binary function, on the other hand, must take exactly two arguments, without regard to currying or partial application.

const sum = (a, b) => a + b

const arity = sum.length
console.log(arity) // 2

// The arity of sum is 2

Higher-Order Functions

A function that takes a function as an argument and/or returns a function.

const filter = (predicate, xs) => {
  const result = []
  for (let idx = 0; idx < xs.length; idx++) {
    if (predicate(xs[idx])) {
      result.push(xs[idx])
    }
  }
  return result
}

const is = (type) => (x) => Object(x) instanceof type

filter(is(Number), [0, '1', 2, null]) // [0, 2]

Partial Application

Partial application means creating a new function by pre-filling some of the original function's arguments.

// Helper to create partially applied functions
// Takes a function and some arguments
const partial = (f, ...args) =>
  // returns a function that takes the rest of the arguments
  (...moreArgs) =>
    // and calls the original function with all of them
    f(...args, ...moreArgs)

// Something to apply
const add3 = (a, b, c) => a + b + c

// Partially applying `2` and `3` to `add3` gives you a one-argument function
const fivePlus = partial(add3, 2, 3) // (c) => 2 + 3 + c

fivePlus(4) // 9

You can also use Function.prototype.bind in JS to partially apply a function:

const add1More = add3.bind(null, 2, 3) // (c) => 2 + 3 + c

By preparing intermediate data in advance, partial application helps you build simpler functions out of more complex ones. Curried functions automatically perform partial application.

Currying

The process of converting a function that takes multiple arguments into a function that takes them one at a time.

Each time the function is called, it accepts a single argument and returns a function that accepts one more argument, until all the arguments have been supplied.

const sum = (a, b) => a + b

const curriedSum = (a) => (b) => a + b

curriedSum(40)(2) // 42.

const add2 = curriedSum(2) // (b) => 2 + b

add2(10) // 12

Auto Currying

The transformation of a function that takes multiple arguments into a new function. If you call the new function with fewer arguments than expected, it returns a function that accepts the remaining arguments. Once the function has received the correct number of arguments, it executes.

Underscore, lodash, and ramda all provide a curry function.

const add = (x, y) => x + y

const curriedAdd = _.curry(add)
curriedAdd(1, 2) // 3
curriedAdd(1) // (y) => 1 + y
curriedAdd(1)(2) // 3

Further reading

• Favoring Curry
• Hey Underscore, You're Doing It Wrong!

Function Composition

Combining two functions to form a new function, where the output of the first function becomes the input of the second.

const compose = (f, g) => (a) => f(g(a)) // Definition
const floorAndToString = compose((val) => val.toString(), Math.floor) // Usage
floorAndToString(121.212121) // '121'

Purity

A function is pure if the value it returns is determined solely by its input values, and it produces no side effects.

const greet = (name) => 'Hi, ' + name

greet('Brianne') // 'Hi, Brianne'

As opposed to:

let greeting

const greet = () => {
  greeting = 'Hi, ' + window.name
}

greet() // "Hi, Brianne"

Side effects

A function has side effects if, in addition to returning a value, it interacts with (reads from or writes to) external mutable state.

const differentEveryTime = new Date()

console.log('IO is a side effect!')

Idempotent

A function is idempotent if applying it again to its own result produces the same result.

f(f(x)) ≍ f(x)

Math.abs(Math.abs(10))

sort(sort(sort([2, 1])))

Point-Free Style

Writing functions whose definitions don't explicitly name the arguments they use. This style usually requires currying or another higher-order function (or, more generally, tacit programming).

// Given
const map = (fn) => (list) => list.map(fn)
const add = (a) => (b) => a + b

// Then

// Not points-free - `numbers` is an explicit argument
const incrementAll = (numbers) => map(add(1))(numbers)

// Points-free - The list is an implicit argument
const incrementAll2 = map(add(1))

The function incrementAll defines and uses the parameter numbers, so it's not point-free. incrementAll2 simply combines functions and values without mentioning any arguments — it is point-free.

Point-free function definitions look like ordinary assignments without function or =>.

Predicate

A predicate is a function that returns true or false based on the value it's given. A common use for a predicate is as the callback for an array filter.

const predicate = (a) => a > 2

;[1, 2, 3, 4].filter(predicate) // [3, 4]

Categories

Objects with functions that obey certain rules. Monoids, for example.

Value

Anything that can be assigned to a variable.

5
Object.freeze({name: 'John', age: 30}) // The `freeze` function enforces immutability.
;(a) => a
;[1]
undefined

Constant

A variable that cannot be reassigned once defined.

const five = 5
const john = {name: 'John', age: 30}

Constants are referentially transparent. That is, they can be replaced with the values they represent without affecting the outcome.

With the constants from the previous listing, the following expression will always return true.

john.age + five === ({name: 'John', age: 30}).age + (5)

Functor

An object that implements a map function which, while running over every value in the object, produces a new object, and obeys two rules:

// preserves identity
object.map(x => x) === object

and

// is composable
object.map(x => f(g(x))) === object.map(g).map(f)

(f, g are arbitrary functions)

In JavaScript, Array is a functor because it obeys these rules:

[1, 2, 3].map(x => x) // = [1, 2, 3]

and

const f = x => x + 1
const g = x => x * 2

;[1, 2, 3].map(x => f(g(x))) // = [3, 5, 7]
;[1, 2, 3].map(g).map(f)     // = [3, 5, 7]

Pointed Functor

An object with an of function that puts any single value into it. ES2015 adds Array.of, making arrays a pointed functor.

Array.of(1) //  

Lift

Lifting is when you place a value into an object such as a functor. If you lift a function into an applicative functor, you can then make it operate on values that also live inside that functor.

Some implementations have a function called lift or liftA2 to make running functions over functors easier.

const liftA2 = (f) => (a, b) => a.map(f).ap(b)

const mult = a => b => a * b

const liftedMult = liftA2(mult) // this function now works on functors like array

liftedMult([1, 2], [3]) // [3, 6]
liftA2((a, b) => a + b)([1, 2], [3, 4]) // [4, 5, 5, 6]

Lifting a one-argument function and applying it does the same thing as map.

const increment = (x) => x + 1

lift(increment)([2]) // [3]
;[2].map(increment) // [3]

Referential Transparency

An expression is referentially transparent if it can be replaced with its value without changing the behavior of the program.

For example, given the function greet:

const greet = () => 'Hello World!'

Any invocation of greet() can be replaced with Hello World!, so this function is referentially transparent.

Lambda

An anonymous function that can be treated as a value.

;(function (a) {
  return a + 1
})

;(a) => a + 1

Lambdas are often passed as arguments to higher-order functions.

[1, 2].map((a) => a + 1) // [2, 3]

You can assign a lambda to a variable.

const add1 = (a) => a + 1

Lambda Calculus

A branch of computer science that uses functions to build a universal model of computation.

Lazy evaluation

A call-by-need evaluation mechanism that delays evaluating an expression until its value is actually needed. In functional languages, this makes it possible to build structures such as infinite lists, which normally aren't possible in imperative languages where the order of commands matters.

const rand = function*() {
  while (1 < 2) {
    yield Math.random()
  }
}

const randIter = rand()
randIter.next() // Each call gives a random value; the expression is evaluated on demand.

Monoid

An object with a function that "combines" it with another object of the same type. A simple monoid is the addition of numbers:

1 + 1 // 2

In this case, the number is the object and + is the function.

There must also be an identity value such that combining a value with it does not change the value. For addition, that identity is 0.

1 + 0 // 1

It's also required that the grouping of operations does not affect the result (associativity):

1 + (2 + 3) === (1 + 2) + 3 // true

Array concatenation is also a monoid:

;[1, 2].concat([3, 4]) // [1, 2, 3, 4]

The identity value here is an empty array []

;[1, 2].concat([]) // [1, 2]

If identity and composition functions exist, functions themselves form a monoid:

const identity = (a) => a
const compose = (f, g) => (x) => f(g(x))

foo is any single-argument function.

compose(foo, identity) ≍ compose(identity, foo) ≍ foo

Monad

A monad is an object with of and chain functions. chain is like map, except it flattens nested objects from the resulting output.

// Implementation
Array.prototype.chain = function (f) {
  return this.reduce((acc, it) => acc.concat(f(it)), [])
}

// Usage
;Array.of('cat,dog', 'fish,bird').chain((a) => a.split(',')) // ['cat', 'dog', 'fish', 'bird']

// Contrast to map
;Array.of('cat,dog', 'fish,bird').map((a) => a.split(',')) // [['cat', 'dog'], ['fish', 'bird']]

of is also known as return in other functional languages.
chain is also known as flatmap and bind in other languages.

Comonad

An object with extract and extend functions.

const CoIdentity = (v) => ({
  val: v,
  extract () {
    return this.val
  },
  extend (f) {
    return CoIdentity(f(this))
  }
})

Extract takes a value out of a functor.

CoIdentity(1).extract() // 1

Extend runs a function on the comonad. The function must return the same type as the comonad.

CoIdentity(1).extend((co) => co.extract() + 1) // CoIdentity(2)

Applicative Functor

An object with an ap function. ap applies a function contained in one object to a value contained in another object of the same type.

// Implementation
Array.prototype.ap = function (xs) {
  return this.reduce((acc, f) => acc.concat(xs.map(f)), [])
}

// Example usage
;[(a) => a + 1].ap([1]) //  

This is useful when you have two objects and need to apply a binary operation to their contents.

// Arrays that you want to combine
const arg1 = [1, 3]
const arg2 = [4, 5]

// combining function - must be curried for this to work
const add = (x) => (y) => x + y

const partiallyAppliedAdds = [add].ap(arg1) // [(y) => 1 + y, (y) => 3 + y]

This gives you an array of functions that you can call with ap to get the result:

partiallyAppliedAdds.ap(arg2) // [5, 6, 7, 8]

Morphism

A transformation function.

Endomorphism

A function whose input and output are of the same type.

// uppercase :: String -> String
const uppercase = (str) => str.toUpperCase()

// decrement :: Number -> Number
const decrement = (x) => x - 1

Isomorphism

A pair of transformations between two types of objects that is structural in nature and no data is lost.

For example, 2-dimensional coordinates can be stored as an array [2,3] or an object {x: 2, y: 3}.

// Providing functions to convert in both directions makes them isomorphic.
const pairToCoords = (pair) => ({x: pair[0], y: pair[1]})

const coordsToPair = (coords) => [coords.x, coords.y]

coordsToPair(pairToCoords([1, 2])) // [1, 2]

pairToCoords(coordsToPair({x: 1, y: 2})) // {x: 1, y: 2}

Setoid

An object that has an equals function, which can be used to compare other objects of the same type.

Making an array a setoid:

Array.prototype.equals = (arr) => {
  const len = this.length
  if (len !== arr.length) {
    return false
  }
  for (let i = 0; i < len; i++) {
    if (this[i] !== arr[i]) {
      return false
    }
  }
  return true
}

;[1, 2].equals([1, 2]) // true
;[1, 2].equals([0]) // false

Semigroup

An object that has a concat function that combines it with another object of the same type.

;[1].concat([2]) // [1, 2]

Foldable

An object that has a reduce function that transforms the object into some other type.

const sum = (list) => list.reduce((acc, val) => acc + val, 0)
sum([1, 2, 3]) // 6

Type Signatures

JavaScript functions often include comments indicating the types of their arguments and return values. There are quite a few conventions across the community, but they all look roughly like this:

// functionName :: firstArgType -> secondArgType -> returnType

// add :: Number -> Number -> Number
const add = (x) => (y) => x + y

// increment :: Number -> Number
const increment = (x) => x + 1

If a function accepts another function as an argument, it's wrapped in parentheses.

// call :: (a -> b) -> a -> b
const call = (f) => (x) => f(x)

The letters a, b, c, d indicate that the argument can be of any type. The following version of map takes:

1. a function that transforms a value of type a into a value of another type b
2. an array of values of type a,

and returns an array of values of type b.

// map :: (a -> b) -> [a] -> [b]
const map = (f) => (list) => list.map(f)

Further reading

• Ramda's type signatures
• Mostly Adequate Guide
• What is Hindley-Milner? on Stack Overflow

Union type

Combining two types together into a new one.

JavaScript has no static types, but let's imagine we invent a type NumOrString that is the union of String and Number.

The + operator in JavaScript works on strings and numbers, so we can use our new type to describe its input and output:

// add :: (NumOrString, NumOrString) -> NumOrString
const add = (a, b) => a + b

add(1, 2) // Returns a number 3
add('Foo', 2) // Returns a string "Foo2"
add('Foo', 'Bar') // Returns a string "FooBar"

Union types are also known as algebraic types, tagged unions, or sum types.

There are a couple of libraries in JavaScript that help with defining and using union types.

Product type

A product type combines types together in a way you're probably more familiar with:

// point :: (Number, Number) -> {x: Number, y: Number}
const point = (x, y) => ({x: x, y: y})

It's called a product because the total possible values of the data structure is the product of the different values it holds.

See also: set theory.

Option

A union type with two cases: Some and None. Useful for composing functions that may not return a value.

// Naive definition

const Some = (v) => ({
  val: v,
  map (f) {
    return Some(f(this.val))
  },
  chain (f) {
    return f(this.val)
  }
})

const None = () => ({
  map (f) {
    return this
  },
  chain (f) {
    return this
  }
})

// maybeProp :: (String, {a}) -> Option a
const maybeProp = (key, obj) => typeof obj[key] === 'undefined' ? None() : Some(obj[key])

Use chain to sequence functions that return an Option.

// getItem :: Cart -> Option CartItem
const getItem = (cart) => maybeProp('item', cart)

// getPrice :: Item -> Option Number
const getPrice = (item) => maybeProp('price', item)

// getNestedPrice :: cart -> Option a
const getNestedPrice = (cart) => getItem(obj).chain(getPrice)

getNestedPrice({}) // None()
getNestedPrice({item: {foo: 1}}) // None()
getNestedPrice({item: {price: 9.99}}) // Some(9.99)

Option is also known as Maybe. Some is sometimes called Just. None is sometimes called Nothing.

Pattern Matching

let neg x =
    match x with
    | false -> true
    | true -> false
;;

let neg x =
    if x = false then true
    else false
;;

let rec sum l =
    match l with
    | [] -> 0
    | x :: xs -> x + (sum xs)
;;

type animal = Dog of string | Cat of string ;;

let say x =
    match x with
    | Dog (x) -> x ^ "says 'woof'"
    | Cat (x) -> x ^ "says 'meow'"
;;

/foo|bar/ { foobar++ }

END { print foobar }

First-class object Jump to navigation

# assign a procedure to a variable
var value = proc() =
  echo "value"

value() # call the procedure
var value2 = value
value2() # call the procedure

# the procedure will be passed to another one
proc two(): string =
  return "two"

# the procedure will receive another procedure
proc wrap(x: proc) =
  echo "one"
  echo x()
  echo "three"

# calling the procedure that receives another procedure as input
wrap(two)

# a procedure that returns a procedure
proc closure(x: int): proc =
  proc res(y:int): int =
    return y*y+x
  return res

var result = closure(2) # call the procedure that will return another procedure
echo result(3) # call the inner procedure

Higher-Order Function

Jump to navigationJump to search

def f(x):
    return x + 3

def g(function, x):
    return function(x) * function(x)

print (g(f, 7))

let f x = x + 3

let g func x = (func x) * (func x)

System.Console.WriteLine(g f 7)

var f = (Func<int, int>)((x) => x + 3);

var g = (Func<Func<int, int>, int, int>)((func, x) => func(x) * func(x));

Console.WriteLine(g(f, 7));

f = ->(x) { x+3 }
def g (f, x); f.call( x ) * f.call( x ) end

puts g f,7

def g x; (yield x) * (yield x) end

puts g(7){|x| x+3}

defmodule Hop do
    def twice(f, v) do
        f.(f.(v))
    end
end

add3 = fn(v) -> 3 + v end

IO.puts Hop.twice(add3, 7) #13

f(X) ->
    X + 3.

g(Fun, X) ->
    Fun(X) * Fun(X).

start()->
    Result = g(fun f/1, 7),
    io:format("~p", [Result]).

{$mode objfpc}
type fun = function(x:integer):integer;

function f(x:integer):integer;
begin
	f:= x+3;
end;

function g( func:fun; x:integer):integer;
begin
        g:= func(x)*func(x);
end;

begin
     write(g(@f, 7));
end.

<?php
$f = function (int $x): int {
    return $x + 3;
};

function g(callable $function, int $x): int
{
    return $function($x)*$function($x);
}

print g($f, 7);

(defn g [f x]
  (* (f x) (f x)))

(print (g #(+ 3 %) 7))

local f = function(func, x)
  return func(x) * func(x)
end
print(f(function(x) return x + 3 end, 7))

f func x = (func x)^2
main = print $ f (+3) 7

def f(x: Int) = x + 3

def g(f: Int ⇒ Int, x: Int) = f(x) * f(x)

println(g(f, 7))

def g(f: Int ⇒ Int, x: Int) = f(x) * f(x)

println(g(_ + 3, 7))

my $f=sub { $_[0]+3 };
sub g {
    $_[0]->($_[1])*$_[0]->($_[1])
}
say g $f,7

// ES5
var f = function (x) {
    return x + 3;
};
var g = function (func, x) {
  return func(x) * func(x);
};
console.log(g(f, 7));

// ES6
let f = x => x + 3;
let g = (func, x) => func(x) * func(x);
console.log(g(f, 7));

func f(_ x: Int) -> Int {
    return x + 3
}

func g(_ function: (Int) -> Int, x: Int) -> Int {
    return function(x) * function(x)
}

print(g(f, x: 7))

let g: (Int, (Int) -> Int) -> Int = { (x, f) in f(x) * f(x) }
print(g(7) { x in x + 3 })

// Using shorthand parameter names              
let g: (Int, (Int) -> Int) -> Int = { $1($0) * $1($0) }
print(g(7) { $0 + 3 })

proc f(x: int): int =
  return x + 3

proc g(function: proc, x: int): int =
  return function(x) * function(x)

echo g(f, 7)

Function<Integer, Integer> f = x -> x + 3;

BiFunction<Function<Integer, Integer>, Integer, Integer> g = (func, x) -> func.apply(x) * func.apply(x);

System.out.println(g.apply(f, 7));

f = { x -> x + 3 }
g = { func, x -> func(x) * func(x) }

System.out.println(g(f, 7))

intf(intx){returnx+3;}
intg(int(*func)(int),intx){returnfunc(x)*func(x);}
printf("%d",g(f,7));

intf(intx){returnx+3;}
template<typename T>
intg(T&&func,intx){returnfunc(x)*func(x);}
std::cout<<g(f,7);

autof=[](autox){returnx+3;}
autog=[](autof,autox){returnf(x)*f(x);}
std::cout<<g(f,7);

(define (f x)(+ x 3))
(define (g f x)(* (f x) (f x)))
(print (g f 7))

fun f(x:Int):Int= x+3
fun g(function:(y:Int)->Int, x:Int):Int = function(x)*function(x)

println(g(::f,7))

func f(x int) int {
	return x + 3
}

func g(function func(x int) int, x int) int {
	return function(x) * function(x)
}

fmt.Print(g(f, 7))

#! /bin/bash

function f(){
    X=$1;
    echo $(( $X + 3 ));
}

function g(){
    FUNCTION=$1;
    X=$2;
    echo $(( $( ${FUNCTION} ${X} ) * $( ${FUNCTION} ${X} ) ));
}

echo "$( g f 7 )";