Functional Programming

High-level view

A program (or just a single function) is a precise specification of a process detailed-enough to be executed by an abstract machine.

An algorithm is a formalized (well-defined and precise) general procedure (a particular sequence of steps), to be implemented in all sufficient and necessary details in more than one programming language.

Representations are parts of implementation details and should be hidden behind abstraction barriers which are sets of interfaces (particular function signatures).

These functions are partitioned into semi-independent (loose-coupled) modules, where each module exports its public interface (a particular set of signatures to be used by a “client”).

A pile is not the same as the things it is made of (especially when it is made of different kinds of things or “objects”).

A molecule is not the same as the individual atoms (it has its own unique shape and the properties that emerge from it).

This is the beginning of a categorical thinking. Compounds are different kinds of things, and this is what typing is about - to partition the universe of “kinds of things” (values).

A Set is a generalization of a simplest category (which has a minimal or no structure whatsoever).

It is said that categories (in the context of the Category Theory, at least some useful parts of it) has more algebraic structure that mere a Set (the most general abstraction, well, after a Number, out there).

Both sets and categories (to a much lesser extent) are relevant to Functional Programming (as a pradigm).

Structured programming - programming with

sequencing (nesting of expressions and function calls)
branching (if, cond)
recursion (looping)
pattern-matching everywhere

And this is really all that is there (nothing more to take away).

Functional (extended lambda calculus - system F (w))

everything is an expression (can be reduced to a value)
mathematical functions (closures)
each value has a type (a static environment)
everything is immutable (just bindings)

Modular (with abstract interfaces, algebraic types)

a separate module for every major type (loosely coupled)
a stable abstract interface for each module (ADTs)
representation and implementation are hidden (irrelevant)
data definitions and function definitions (inside a module)

Algebraic types

sum-types and pattern-mating on them
product-types (records or “structs”)
function types (or exponentials)

Beautiful tools of the trade

currying
partial application
high-order functions
uniform pattern-matching on sum-types
Monads (as abstraction barriers - actual ADTs)

When there is nothing mode to remove

types: capture the actual concepts or patterns
functions: do just one thing but do it well (just right)
modules: just one ADT, but done right

Embeded DSLs

sets of high-order functions based on domain-specific ADTs
this is the way to design rich libraries

Interfaces

sets of type-signatures.
simple, consistent at a use-side

Protocols

sets of rules and related data types (this!)
corresponds to the physical constraints of the environment
could be thought of as contracts or even laws

Principles

Design with modules and interfaces (higher level) which corresponds to the core parts of the mathematical model of the domain.

Ideally, each module corresponds to a major concept in the domain.

Types first (the Typeful meme). Not just types, but Algebraic types (sum, product) and Abstract Data Types (data-constructors, pattern-matching, no selectors).

Parameterized (polymorphic) types, Higher-kinded types, defined as instances of common and standard type-classes.

Interfaces (types again) before implementations (the Domain-driven meme).

Write down the types (of functions) you’re going to use before implementation.
Write your type definitions before writing the logic of your computations.
Write a first draft of your .mli before working on the .ml.
Write a draft of module exprorts in .hs first.

Design

Function type-signatures and module-signatures provide a lightweight tool for constructing a skeleton (a hierarchy of layers, layout) of your design in a way that helps clarify your thought, goals and intent.

Modules

Factor out the key functionality into a separate module with an explicit interface (signature).

Alternative implementations (structures) for a single signature (a set of interfaces).

Uniform interfaces (consistency)
A module for (almost) every type.
implicit namespaces.

the primary type of a given module should be called t.