Functional Programming terminology

Based on the “Learning Functional Programming in Scala” book by Alvin Alexander.  Below are all extracts (quotes) from the book.

PURE FUNCTION

A function that depends only on its declared input parameters and its algorithm to produce its output. It does not read any other values from “the outside world” — the world outside of the function’s scope — and it does not modify any values in the outside world.

1. Output depends only on input
2. No side effects

APPLY

Functional programmers like to say that they apply functions to input data to get a desired output. As you saw, using the word “apply” in the previous discussion was quite natural.

IDEMPOTENT FUNCTION

The terms idempotent and deterministic are similar to a favorite phrase of mine: you can call a pure function an infinite number of times and always
get the same result.

REFERENTIAL TRANSPARENCY

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

FUNCTION LITERAL

The bold part is a function literal:

xs.map(x => x * 2)

MAP

Applying a function over a collection of items

FUNCTOR

Things that can be mapped over

COMBINATOR

Per the Haskell wiki, this has two meanings, but the common meaning is, “a style of organizing libraries centered around the idea of combining things.” This refers to being able to combine functions together like a Unix command pipeline, i.e.,

ps aux | grep root | wc -l

HIGHER-ORDER FUNCTION

A function that takes other functions as
parameters, or whose result is a function.

LAMBDA

Another word for “anonymous function”

FREE VARIABLE

Is a variable used within a function, which is
neither a formal parameter to the function nor defined in the
function’s body.

FUNCTIONAL COMPOSITION

val x = doThis(a)
 .thenThis(b)
 .andThenThis(c)
 .doThisToo(d)
 .andFinallyThis(e)

EXPRESSION-ORIENTED PROGRAMMING

When every line of code has a return value it is said that you are writing expressions, and using an EOP style. In contrast, statements are lines of code that do not have return values, and are executed for their side effects. When see statements in code you should think, “This is imperative code, not FP code.”

CURRIYNG

All that the theory of currying means is that a function that takes multiple arguments can be translated into a series of function calls that each take a single argument. In pseudocode, this means that an expression like this:
result = f(x)(y)(z)
is mathematically the same as something like this:
f1 = f(x)
f2 = f1(y)
result = f2(z)

That’s all it means. Rationale: there are analytical techniques that can only be applied to functions with a single argument.

PARTIALLY-APPLIED FUNCTION

The plus2 function below is a partially-applied function:

scala> def plus(a: Int)(b: Int) = a + b
plus: (a: Int)(b: Int)Int
scala> def plus2 = plus(2)(_)
plus2: Int => Int
scala> plus2(2)
res0: Int = 4
Two definitions from this online JavaScript course:
1) Application: The process of applying a function to its arguments in order to produce a return value.
As in algebra, in FP you say that “a function is applied to its arguments,” so “Application” in this context can also be called “Full Application,” or “Complete Application.”
2) Partial Application: This is the process of applying a function to
some of its arguments. A partially-applied function gets returned for later use. In other words, a PAF is a function that takes a function with multiple parameters and returns a function with fewer parameters.

TAIL RECURSION

A tail-recursive function is just a function whose very last action is a call to itself. When you write your recursive function in this way, the Scala compiler can optimize the resulting JVM bytecode so that the function requires only one stack frame — as opposed to one stack frame for each level of recursion… Martin Odersky explains tail-recursion in Scala: “Functions which call themselves as their last action are called tail-recursive. The Scala compiler detects tail recursion and replaces it with a jump back to the beginning of the function, after updating the function parameters with the new values … as long as the last thing you do is calling yourself, it’s automatically tail-recursive (i.e., optimized).”

import scala.annotation.tailrec

def sum(list: List[Int]): Int = {
  @tailrec
  def sumWithAccumulator(list: List[Int], accumulator: Int): Int = {
    list match {
      case Nil => accumulator
      case x::xs => sumWithAccumulator(xs, accumulator + x)
    }
  }
  sumWithAccumulator(list, 0)
}

val l = (0 to 1000000).toList
val s = sum(l)

PREDICATE

A function that returns a Boolean value is known as a predicate.

Leave a Reply

Your email address will not be published. Required fields are marked *