Functional Programming - ttulka/programming GitHub Wiki

Object-oriented programming makes code understandable by encapsulating moving parts. Functional programming makes code understandable by minimizing moving parts. -- Michael Feathers

Building Blocks

Functions are:

  1. Total: They return an output for every input.
  2. Deterministic: They return the same output for the same input.
  3. Pure: Their only effect is computing the output.
  • In functional languages, a name is only ever associated with one value.
  • In functional languages, there is no necessary execution order.
  • Functional languages allow functions to be treated as values.

In functional languages, because there is no assignment, it is not possible to change independently sub-structures of global structures. Instead, entire data structures are passed explicitly as actual parameters to functions for substructure changes and the entire changed structure is then passed back again to the calling function. This means that function calls in a functional program are larger than their equivalents in an imperative program because of these additional parameters. However, it has the advantage of ensuring that structure manipulation by functions is always explicit in the function definitions and calls. This makes it easier to see the flow of data in programs.

OO makes code understandable by encapsulating mutable state. FP makes code understandable by minimizing mutable state. (Michael Feathers)

Pure function is one that has no side effects: it references no other mutable class fields, doesn’t set any values other than the return value, and relies only on the parameters for input.

Imperative programming often forces you to complect your tasks so that you can fit them all within a single loop, for efficiency. Functional programming via higher-order functions such as map() and filter() allows you to elevate your level of abstraction, seeing problems with better clarity.

  • FP constructs make it easier to reuse code at a more atomic level.
  • FP prefers a few key data structures (such as list, set, and map) with highly optimized operations on those data structures.
  • FP describes programs as expressions and transformations, modeling mathematical formulas, and tries to avoid mutable state.
  • FP tends to deal with values, preferring to react to return values that indicate an error rather than interrupt program flow (throwing an exception is a side effect that causes unusual /exceptional/ program flow).
public static Either<Exception, Integer> parseInteger(String s) {
  if (s.matches("[0-9]+"))
    return Either.right(Integer.parseInt(s));
  else 
    return Either.left(new Exception("Invalid number format."));
}
public static Either<Exception, Integer> divide(int x, int y) {
  try {
    return Either.right(x / y);
  } catch (Exception e) {
    return Either.left(e); }
}

Web programming is a terrific fit for functional programming: one can view the entire Web as a series of transformations from request to response.

It is better to have 100 functions operate on one data structure than 10 functions on 10 data structures. (Alan Perlis)

  • Prefer a few data structures and many operations.

A common source of confusion in Java is the presence of null: is it a legitimate return value or does it represent the absence of a value? In many functional languages (Scala included), that ambiguity is avoided by the Option class, which contains either None, indicating no return, or Some, containing the returned values.

public static Option<Double> divide(double x, double y) {
  if (y == 0)
    return Option.none();
  return Option.some(x / y);
}

One of the advantages of switching from an imperative to a functional style lies in the runtime’s ability to make efficiency decisions for you.

Instead of thinking of a list as indexed slots, think of it as a combination of the first element in the list (the head) plus the remainder of the list (the tail).

  • Recursion allows you to cede state management to the runtime.
def filterR(list, pred) {
  if (list.size() == 0) return list
  if (pred(list.head()))
    [] + list.head() + filterR(list.tail(), pred)
  else
    filterR(list.tail(), pred)
}
  • Focus on results over steps.
  • Filter/fold rather than iterate.

Useful Things: filter, map, reduce and fold (collecting).

First-class functions - The language supports passing functions as arguments to other functions, returning them as the values from other functions, and assigning them to variables or storing them in data structures.

def shout(text):
    return text.upper()
 
print shout('Hello')
 
yell = shout
 
print yell('Hello')

Closures allow us to model behavior by encapsulating both code and context into a single construct.

  • Capture the context, not the state.
  • Objects are data with functions. Closures are functions with data.

The key concept is that when you define a function, it can refer to not only its own local variables, but also to everything outside of the context of the function:

function newCounter() {
  let count = 0;
  return function() {
    return ++count;
  };
} 
const nc = newCounter();
console.log(nc()); // 1
console.log(nc()); // 2
console.log(nc()); // 3

Even after function newCounter exits, the inner function still has access to count, but that variable is not accessible to any other parts of your code.

Currying describes the conversion of a multiargument function into a chain of single-argument functions. It describes the transformation process, not the invocation of the converted function. The caller can decide how many arguments to apply, thereby creating a derived function with that smaller number of arguments.

  • Example: the fully curried version of the process(x, y, z) function is process(x)(y)(z) 
def product = { x, y -> x * y }
def quadrate = product.curry(4)
println "4x5: ${quadrate.call(5)}"

Partial application describes the conversion of a multiargument function into one that accepts fewer arguments. It partially applies some arguments to a function, returning a function with a signature that consists of the remaining arguments.

  • Example: using partial application for a single argument on process(x, y, z) yields a function that accept two arguments: process(y, z) 
def adder = { x, y -> x + y}
def incrementer = adder.curry(1)
println "increment 7: ${incrementer(7)}" // 8

Memoization is a feature built into a programming language that enables automatic caching of recurring function-return values.

Lazy evaluation - deferral of expression evaluation for as long as possible.

Monad is a set of a parameterized type M<T>, a “unit” function T -> M<T> and a “bind” operation: M<T> bind T -> M<U> = M<U>. In Java Stream class and Optional class are monads:

  • Parameterized type: Optional<T>
  • unit: Optional.of()
  • bind: Optional.flatMap() 
personMap.find("Name")
   .flatMap(Person::getAddress)
   .flatMap(Address::getCity)
   .ifPresent(ThisClass::process);

Tail-call optimization - recursive definition in which the recursive call is the last thing that happens in the function.

// tail-recursive factorial
long factorialTailRecursion(long n) {
    return factorialHelper(1, n);
}
long factorialHelper(long acc, long n) {
    return n == 1 ? acc : factorialHelper(acc * n, n - 1);
}

Functors

A functor data type is something you can map over. It’s a container which has an interface which can be used to apply a function to the values inside it. When you see a functor, you should think “mappable”. Functor types are typically represented as an object with a .map() method that maps from inputs to outputs while preserving structure. In practice, “preserving structure” means that the return value is the same type of functor (though values inside the container may be a different type).

A functor supplies a box with zero or more things inside, and a mapping interface. An array is a good example of a functor, but many other kinds of objects can be mapped over as well, including streams, trees, objects, promises (mapping function then), etc.

Endofunctors

An endofunctor is a functor that maps from a category back to the same category.

  • A functor can map from category to category: X -> Y
  • An endofunctor maps from a category to the same category: X -> X
  • A monad is just a monoid in the category of endofunctors

Example: Chain of Operations

Kick off a chain of operations, but only if the value inside the functor is not undefined or null:

// create the predicate
const exists = x => (x.valueOf() !== undefined && x.valueOf() !== null);
// create the functor
const ifExists = x => ({
  map: fn => exists(x) ? x.map(fn) : x
});
const add1 = n => n + 1;
const double = n => n * 2;

ifExists(Identity(undefined)).map(trace)   // Nothing happens...

ifExists(Identity(null)).map(trace)       // Still nothing...

ifExists(Identity(20))
  .map(add1)
  .map(double)
  .map(trace)                              // 42

Monads

  • Monadic value: wraps a value with a context that talks to the composer and possibly accumulates state
  • Mondaic function: a pure function returning a monadic value
  • Composer: a pure function that composes a monadic value with a monadic function

Monad Examples

The [] Monad: Counter 

[x, n]

f(x): x -> [y, k]

[x, n] ([]) f -> [y, k + n]

f()  = [3, 1]
g(x) = [x + 1, 2]
h(x) = [x * 2, 3]

f ([]) g ([]) h  ==>  [8, 6]

The <> Monad: Exception 

<x, E>  (E: success|error)

f(x): x -> <y, E>

<x, E> (<>) f -> success: f(x) | error: <_, error> 

f(x) = <3, success>
g(x) = <_, error>
h(x) = <x * 2, success>

f (<>) g (<>) h  ==>  <_, error>
f (<>) h         ==>  <6, success>

The {} Monad: IO 

{op, x}  (op: print|read|noop)

f(x): x -> {op', y}

{op, x} ({}) f -> print: print x, f(_) | read: read r, f(r) | noop: f(x) 

p()  = {print, "What's your name?"}
r()  = {read, _}
f(x) = {print, "Hello, " + x + "!"}

p ({}) r ({}) f

Any function that wants to call an IO sequence has to return such an expression as its return value all the way up to the main function of the program and the runtime evaluates it lazily.

Design Patterns in Functional Languages

Template Method

def process() {
  checkCredit?.call()
  checkInventory?.call()
  ship?.call()
}

Strategy

MyInterface impl = new MyInterface() {
  public void process() { ... }
};

Factory and Currying

  • Use currying to construct specific functions from general ones.
def adder = { x, y -> x + y}
def incrementer = adder.curry(1)

Origins

The propositional calculus is a system with true and false as basic values and with and, or, not and so on as basic operations. Names are used to stand for arbitrary truth values. Within propositional calculus it is possible to prove whether or not an arbitrary expression is a theorem, always true, by starting with axioms, elementary expressions which are always true, and applying rules of inference to construct new theorems from axioms and existing theorems. Propositional calculus provides a foundation for more powerful logical systems. It is also used to describe digital electronics where on and off signals are represented as true and false, and electronic circuits are represented as logical expressions.

The predicate calculus extends propositional calculus to enable expressions involving non-logical values like numbers or sets or strings. This is through the introduction of predicates to generalise logical expressions to describe properties of non-logical values, and functions to generalise operations on non-logical values. It also introduces the idea of quantifiers to describe properties of sequences of values, for example all of a sequence having a property, universal quantification, or one of a sequence having a property, existential quantification. Additional axioms and rules of inference are provided for quantified expressions.

An important difference between Turing machines, and recursive functions and λ calculus is that the Turing machine approach concentrated on computation as mechanised symbol manipulation based on assignment and time ordered evaluation. Recursive function theory and λ calculus emphasised computation as structured function application. They both are evaluation order independent.

Today, λ calculus and recursive function theory are the backbones of functional programming but they have wider applications throughout computing.

Lambda calculus syntax

<expression> ::= <name> | <function> | <application>
<name> ::= non-blank character sequence`
<function> ::= l <name> . <body>
<body> ::= <expression>
<application> ::= ( <function expression> <argument expression> )
<function expression> ::= <expression>
<argument expression> ::= <expression>

Category Theory

Category theory provides a meta-language for reasoning about computer programs at a declarative level. It also encourages reasoning about problem specification before it is cast into code.

A category theory consists of objects and morphisms (arrows) which can be composed, and the composition is associative. Every object has an identity arrow that serves as a unit under composition.

You can build categories just by connecting objects with arrows. You can imagine starting with any directed graph and making it into a category by simply adding more arrows. First, add an identity arrow at each node. Then, for any two arrows such that the end of one coincides with the beginning of the other (in other words, any two composable arrows), add a new arrow to serve as their composition. Every time you add a new arrow, you have to also consider its composition with any other arrow (except for the identity arrows) and itself. You usually end up with infinitely many arrows, but that’s okay.

Another way of looking at this process is that you’re creating a category, which has an object for every node in the graph, and all possible chains of composable graph edges as morphisms.

The initial object is the object that has one and only one morphism going to any object in the category.

The terminal object is the object with one and only one morphism coming to it from any object in the category.

  • A category is a collection of objects and arrows between objects (where “object” can mean literally anything).
  • Arrows are known as morphisms. Morphisms can be thought of and represented in code as functions.
  • For any group of connected objects, a -> b -> c, there must be a composition which goes directly from a -> c.
  • All arrows can be represented as compositions (even if it’s just a composition with the object’s identity arrow). All objects in a category have identity arrows.

Monoids

Monoid is defined as a set with a binary operation. All that’s required from this operation is that it’s associative, and that there is one special element that behaves like a unit with respect to it.

For instance, natural numbers with zero form a monoid under addition. Associativity means that:

(a + b) + c = a + (b + c)

The neutral element is zero, because:

0 + a = a
a + 0 = a

Commutativity is not part of the definition of a monoid. For instance, string concatenation is not commutative and yet it forms a monoid.

Every monoid can be described as a single object category with a set of morphisms that follow appropriate rules of composition.

Monads

A monad is a way of composing embellished functions. It’s not about side effects or state. It’s about composition.

Definition of a monad using Kleisli composition:

class Monad m where
    (>=>) :: (a -> m b) -> (b -> m c) -> (a -> m c)
    return :: a -> m a

Interactive Input

A function like getChar, if it were to return a character typed at the keyboard, couldn’t be pure. But what if it returned the character inside a container? As long as there was no way of extracting the character from this container, we could claim that the function is pure. Every time you call getChar it would return exactly the same container. Conceptually, this container would contain the superposition of all possible characters.

It’s just like the box with the Schrödinger’s cat inside — except that there is no way to open or peek inside the box. The box is defined using the special built-in IO functor.

getChar could be declared as a Kleisli arrow:

getChar :: () -> IO Char

Being a functor, IO lets you manipulate its contents using fmap. And, as a functor, it can store the contents of any type, not just a character. The real utility of this approach comes to light when you consider that, in Haskell, IO is a monad. It means that you are able to compose Kleisli arrows that produce IO objects.

You might think that Kleisli composition would allow you to peek at the contents of the IO object (thus “collapsing the wave function,” if we were to continue the quantum analogy). Indeed, you could compose getChar with another Kleisli arrow that takes a character and, say, converts it to an integer. The catch is that this second Kleisli arrow could only return this integer as an (IO Int). Again, you’ll end up with a superposition of all possible integers. And so on. The Schrödinger’s cat is never out of the bag. Once you are inside the IO monad, there is no way out of it.

What can you do with the result of a Kleisli arrow, the IO object, other than compose it with another Kleisli arrow? Well, you can return it from main. In Haskell, main has the signature:

main :: IO ()

and you are free to think of it as a Kleisli arrow:

main :: () -> IO ()

From that perspective, a Haskell program is just one big Kleisli arrow in the IO monad. You can compose it from smaller Kleisli arrows using monadic composition. It’s up to the runtime system to do something with the resulting IO object (also called IO action).

Notice that the arrow itself is a pure function — it’s pure functions all the way down. The dirty work is relegated to the system. When it finally executes the IO action returned from main, it does all kinds of nasty things like reading user input, modifying files, printing obnoxious messages, formatting a disk, and so on. The Haskell program never dirties its hands.

So, in reality, the execution of a program is an interleaving of pure (Haskell) and dirty (system) code.

Interactive Output

The same IO monad is used to encapsulate interactive output. Real World is supposed to contain all output devices.

putStr :: String -> IO ()

Conceptually, in this program:

main :: IO ()
main = do
    putStr "Hello "
    putStr "World!"

the action that prints “World!” receives, as input, the Universe in which “Hello ” is already on the screen. It outputs a new Universe, with “Hello World!” on the screen.

Functional Java

Java 9 Enhancements

  • Enhanced filter: takeWhile, dropWhile 
// get items with the value greater than 100
items.stream()
    //.filter(it -> it.value() > 100)    // filter must iterate thru all the items
    .takeWhile(it -> it.value() > 100)   // returns items when the predicate is true, drops all remaining when first evaluates to false; makes sense when items are already sorted
    .collect(toList());

// get items with the value greater than 100
items.stream()
    //.filter(it -> it.value() <= 100)    // filter must iterate thru all the items
    .dropWhile(it -> it.value() <= 100)   // drops items when the predicate is false, returns all remaining when first evaluates to true; makes sense when items are already sorted
    .collect(toList());

Functional Tree Structure Update

Tree fupdate(String key, int newval, Tree tree) {
    return (tree == null) 
        ? new Tree(key, newval, null, null) 
        : k.equals(tree.key) 
            ? new Tree(key, newval, tree.left, tree.right) 
            : k.compareTo(tree.key) < 0 
                ? new Tree(tree.key, tree.val, fupdate(key, newval, tree.left), tree.right) 
                : new Tree(tree.key, tree.val, tree.left, fupdate(key, newval, tree.right));
    } }

References

⚠️ **GitHub.com Fallback** ⚠️