Functional Programming

• A programming paradigm is the term for a style of programming. Different paradigms may be better suited to different problems
• A function is a rule that, for each element of a set A of inputs, assigns an output from set B, without necessarily using every element of set B
• Functions take arguments as inputs, apply rules to these arguments, and then return an output. An argument could be any data type or even another function
• Where f: A → B, set A is the domain and set B is the co-domain
• A domain and co-domain are always subsets of objects in a data type
• A first-class object can:

  -be assigned as variables

  -be assigned as arguments

  -appear in expressions

  -be returned in function calls
• In functional programming, functions are first-class objects
• Giving specific inputs to a function is called function application - the function is applied to the provided argument
• If f is the function, A is the input and B is the output, then A → B is its function type. The function type determines the functionality of f. Here, A is the argument type, and B is the result type
• A function only takes one argument. If it appears to take multiple, it is in fact taking one and returning a new function to take in the next argument and so on.

  For example

  integer → integer → integer → integer

  is really

  integer → (integer → (integer → integer))

  where each set of brackets is another function
• Partial application means giving less arguments than a function expects. This can be used to create more specialised functions by binding an argument to a function. Sort of like subroutine calls. Also allows modification of functions without re-writing their definitions
• You can combine two functions to get a new function. This is called composition of functions
• Composition is denoted with ○
• If x: A → B and y: B → C

  Then y ○ x A → C

  The co-domain of x must be the domain of y
• In composition, eg A ○ B, B is applied first, then A
• A higher-order function is a function that takes a function as an argument, returns a function, or does both
• Map takes two arguments, a function and a list. The function is applied to each item of the list, and the output is the resulting list.
• Filter takes two arguments, a predicate and a list. The output is a list consisting only of the elements which match the predicate
• A predicate is a boolean condition, and this could be written directly or as a function
• Fold (or reduce) applies a function recursively to a list to output a single value. It requires an operator, a starting number and a list.
• Fold left just means start from the leftmost value
• A list is a concatenation of a head and a tail
• A head is the first element of a list. A tail is the remainder of the list.
• In functional programming, the values of variables cannot change - they are immutable. This means functions have no side effects, which is ideal for parallel processing.
• Lists can be empty, represented as []. You can test for an empty list using the function null, which will return true or false.
• We can return the length of a list using the function length
• We can prepend items to a list (add them to the front) using : or ++
• We can append items to a list (add them to the end) either by prepending the list we want to append to, or using a function that reverses a list, prepends, and reverses again
• We can return the head or tail of a list using the functions head or tail. You could use a combination of these to receive specific items within a list