Programming in Haskell: Chapter 1 - Introduction to Functional Programming

What is a Functional Language?

• Functional Programming Style: This is a style of programming where the fundamental method of computation is the application of functions to arguments.

• Definition of a Functional Language: A language that explicitly supports and encourages the functional style of programming.

• Definitional Nuance: While opinions differ and a precise definition can be difficult to establish, functional languages are generally characterized by function application as opposed to variable assignment.

Comparative Examples: Summing Integers

• Imperative Approach (Java Example):     * Objective: Summing the integers from $1$ to $10$.     * Code implementation:         * $int \, total = 0;$         * $for \, (int \, i = 1; i \le 10; i++) total = total + i;$     * Computation Method: This approach relies on variable assignment to track and update the state of the sum.

• Functional Approach (Haskell Example):     * Objective: Summing the integers from $1$ to $10$.     * Code implementation:         * $sum [1..10]$     * Computation Method: This approach utilizes function application as the primary mechanism for computation.

Historical Background: 1930s to 1960s

• 1930s (Lambda Calculus): Alonzo Church develops the lambda calculus. This is characterized as a simple but powerful theory of functions that serves as the foundation for functional programming.

• 1950s (Lisp): John McCarthy develops Lisp, recognized as the first functional language. While it drew influence from lambda calculus, it notably retained the use of variable assignments.

• 1960s (ISWIM): Peter Landin develops ISWIM (If You See What I Mean). This is cited as the first pure functional language, based strongly on the lambda calculus and completely omitting assignments.

Historical Background: 1970s to 1980s

• 1970s (FP): John Backus develops FP. This functional language placed a heavy emphasis on higher-order functions and the ability to reason about programs mathematically.

• 1970s (ML): Robin Milner and others develop ML. As the first "modern" functional language, it introduced critical concepts such as type inference and polymorphic types.

• 1970s - 1980s (Lazy Functional Languages): David Turner develops a series of lazy functional languages, which eventually culminated in the creation of the Miranda system.

The Development of Haskell (1987 - Present)

• Origins (1987): An international committee begins the development of Haskell, intended to be a standard lazy functional language. It is defined as an advanced, purely functional programming language.

• Innovation (1990s): Phil Wadler and others introduce two of Haskell's main innovations: type classes and monads.

• Stabilization (2003): The committee publishes the Haskell Report, providing a stable definition of the language.

• Revision (2010): An updated version of the Haskell Report is published to reflect advancements.

• Current State (2010 - present): The language continues to evolve with a focus on:     * Standard distribution and extensive library support.     * Integration of new language features.     * Development of robust programming tools.     * Increased use within industry sectors.     * Significant influence on the design of other programming languages.

A Taste of Haskell: Functional Sorting

• The following example illustrates a recursive sorting algorithm (similar to QuickSort) defined in a functional style:     * $f [] = []$     * $f (x:xs) = f \, ys \mathbin{+\mkern-1mu+} [x] \mathbin{+\mkern-1mu+} f \, zs$     * $\text{where}$         * $ys = [a \mid a \leftarrow xs, a \le x]$         * zs = [b − b \leftarrow xs, b > x]

• Logic Breakdown:     * The function $f$ takes a list. If the list is empty ($[]$), it returns an empty list.     * For a non-empty list with head $x$ and tail $xs$, it recursively sorts the elements smaller than or equal to $x$ ($ys$) and those larger than $x$ ($zs$), then concatenates the results around the pivot $x$.