Functional Programming Basics

Wikipedia Functional Programming

The functional programming paradigm has it's origins in lambda calculus, and treats computation as the evaluation of mathematical functions. It's intended to be more declarative, and thus programs try to express what it's doing, rather than how it's doing it (how it's implemented).

Since FP is mathematical, data generally must be immutable. Consider the following:

// Imperative programming
var x = 5
x = x + 2
x // 7

This statement doesn't make sense in a mathematical sense:

// Math
x = x + 2

//solve for x
x - x = 2
0 = 2

The code x = x + 2 will aways depend on what x is at that time, which may not aways be clear. Immutable data provides performance benefits, and makes code easier to test and reason about.

Although there are many purely functional programming languages, such as Haskell, Clojure, and Elm, many of the core concepts of functional programming can be applied to other multi-paradigm languages.

Concepts

Main concepts:

First-class and higher-order functions

When functions are first-class citizens, they're able to be set to variables and passed around like any other value. Higher-order functions are those that either accept functions as arguments, or return them as results. This allows for powerful coding techniques, such as partial application/currying and composition.

Pure functions

A function is pure if it has no side effects. That means the output of a function is entirely dependent on the inputs. It will not, for example, use a random value or the current date, unless that value is passed in as an argument.

Additionally, the function does not effect some state outside of its scope. All it does is return a value. Therefore, the a pure function called twice with the same arguments will always return the same value. This will allow for caching optimization (memoization).

Pure functions are also thread-safe. Two functions can be run in parallel because they're not changing the data that the other one is using.

Supporting concepts:

Recursion

Since data is immutable in functional programming, you can't keep track of a changing index to iterate through an array. So, FP languages will simply use recursion for looping. A functional looping algorithm simply needs to have a parameter for the index, and call itself with the index plus one to get the next value in the collection. Tail call optimization is useful here to prevent new calls from being added to the stack (and potentially causing a stack overflow error).

Evaluation strategy

Functional languages are often categorized in terms of strict (eager) or non-strict (lazy) evaluation. The difference is that strict evaluation will always evaluates all of a function's arguments before invoking the function, while non-strict evaluation only evaluates arguments that are required to evaluate the function itself.

Type System

Most FP languages have a type system to ensure a program is valid at compile time, but risks false positive errors. Strong compile time type checking helps improve code reliability, but programers must manually declare types for function inputs and outputs. There are several untyped FP languages.

Referential transparency

To prevent side effects, functional programs should not be able to reassign variables.

Consider again:

var x = 5
x = x + 2
x // 7

If x were initially assigned the value 6, then it's final value would be 8. The result is dependent on whatever x is at that time, which can be changed by other processes. It is therefore opaque. A pure function will be referentially transparent as it's clear what it's outputs will be.

Data structures

Basic data structures, such as arrays and hash map will likely be implemented differently in FP languages. This is to ensure the benefits of immutability (persistency, quick copy of objects, thread safety). The result may be that arrays and hash maps that have lookup and update times that are normally constant will be logarithmic instead. Purely functional data structures in non-FP languages generally have inferior time/space performance to that of purely functional languages.