Welcome to Functional Programming: The Practice!

Hello! You've already learned the theoretical foundations of the Functional Programming paradigm (like Domains, Co-domains, and First-Class objects). Now, we’re diving into the exciting part: Writing actual functional programs.

This chapter focuses on the techniques and tools you use when writing code in functional languages, like Haskell (the language used in exam examples). Understanding these concepts—especially recursion and higher-order functions—will change how you think about solving problems!

Don't worry if this feels like a big step up from procedural programming. Functional programming encourages simple, elegant solutions, often using very few lines of code. Let's get started!


3.12.2 Writing Functional Programs: Core Concepts

Functional programming treats computation as the evaluation of mathematical functions, avoiding mutable state and side effects.

1. Defining and Using Basic Functions

In functional programming, defining a function is often straightforward, resembling a mathematical definition.

Key Concept: Function Definition
  • You define a function by specifying its name, its arguments, and the rule it uses to calculate the result.
  • A function must be defined with its argument(s).
  • The process of providing inputs (arguments) to a function is called function application.

Example (in Haskell syntax):

To define a function called add that takes two arguments, a and b, and returns their sum:

add a b = a + b

Calling this function (function application): add 3 4 will produce the result 7.

Arithmetic and Boolean Operations

Functional languages support standard operations. You must be familiar with applying these:

  • Arithmetic Operations: Addition (+), subtraction (-), multiplication (*), division (/), and power (^).
  • Boolean Comparisons: Equal to (==), not equal to (/=), greater than (>), less than (<), greater than or equal to (>=), less than or equal to (<=).
  • Boolean Logic: AND (&&), OR (||), NOT (not).

Key Takeaway: Functional programs are built by applying simple, pure functions to inputs, much like composing formulas in mathematics.


2. Recursion and Pattern Matching

In procedural languages, we usually use iteration (loops) to repeat tasks. In functional languages, recursion (a function calling itself) is the primary method for repetition.

Defining Functions using Recursion

A recursive function definition must always have two parts to prevent it from calling itself forever:

  1. Base Case: The stopping condition. This is the simplest version of the problem that does not require further recursion. It returns a fixed value.
  2. Recursive Case: The rule that breaks the problem down into a smaller instance of itself, moving closer to the base case.

Example: Calculating Factorial (n!)

The factorial of n is \( n \times (n-1) \times ... \times 1 \). The mathematical rule is that \( fact(n) = n \times fact(n-1) \), and the base case is \( fact(0) = 1 \).

In functional code (Haskell):
fact 0 = 1
fact n = n * fact (n - 1)

Common Mistake: Forgetting the base case will lead to infinite recursion!

Pattern Matching

In the factorial example above, how does the compiler know whether to use the first line or the second line? It uses pattern matching.

  • Pattern Matching is the ability of a functional language to compare an input value (or structure) against defined patterns (cases).
  • When you call fact 3, the input 3 does not match the pattern 0, so the second line (the recursive case) is applied.
  • When you call fact 0, the input 0 matches the pattern 0 exactly, and the base case 1 is returned, terminating the recursion.

Key Takeaway: Recursion uses base and recursive cases, and pattern matching determines which case applies based on the input structure or value.


3. Higher-Order Functions (HOFs)

A Higher-Order Function (HOF) is a function that either takes another function as an argument, returns a function as a result, or does both.

HOFs are essential for writing concise and powerful functional code. You need experience with three main HOFs: map, filter, and fold (reduce).

A. Map

The map HOF applies a given function to each element of a list, returning a new list containing the results. The original list is unchanged (this is key to functional purity!).

Analogy: If you have a list of prices [10, 20, 30] and a function addTax, mapping the function over the list gives you [12, 24, 36].

Syllabus Example:

Define a function square x = x * x.

Apply map square [1, 2, 3, 4]

Produces the list: [1, 4, 9, 16]

B. Filter

The filter HOF processes a list to produce a new list containing only those elements from the original list that satisfy a specific condition (predicate function).

Analogy: Filtering a contact list to keep only those people whose age is over 30.

Syllabus Example:

Apply filter (<10) [15, 8, 20, 3] (where (<10) is the condition "less than 10").

Produces the list: [8, 3]

C. Fold (Reduce)

The fold (sometimes called reduce) HOF reduces a list of values down to a single value by repeatedly applying a combining function, starting with an initial value (the accumulator).

Analogy: Totaling the scores from a list of test results. You start the accumulator at 0, and add each score one by one, reducing the list into a single sum.

In Haskell, there are two versions depending on the direction of application, which matters for non-commutative operations (like subtraction):

  • foldl (Fold Left): Starts with the leftmost item and works forward.
  • foldr (Fold Right): Starts with the rightmost item and works backward.

Example: Subtraction (Order matters!)
List: [1, 2, 3, 4], Initial Value: 0, Function: Subtraction (-)

Using foldl: Starts from the left, applying the accumulator first.
\( (((0 - 1) - 2) - 3) - 4 = -10 \)

Using foldr: Starts from the right, applying the initial value to the rightmost element first.
\( 1 - (2 - (3 - (4 - 0))) = -2 \)

Key Takeaway: Map transforms all items, filter selects items based on a condition, and fold combines all items into a single result.


3.12.3 Lists in Functional Programming

Lists are fundamental data structures in functional programming, used extensively in conjunction with HOFs.

1. Defining and Understanding Lists

  • A list stores a sequence of values.
  • Lists are typically represented using brackets, e.g., [7, 2, 1].
  • The empty list is represented simply as [].

2. The Head and Tail Concept

A crucial concept for handling lists recursively is separating the list into two parts: the head and the tail.

  • The Head is the first element of the list. (It is a single element/value).
  • The Tail is the remainder of the list. (It is always another list).

Analogy: Imagine a train. The Head is the engine. The Tail is the list of all remaining carriages.

In functional languages, a list is often written as a concatenation of its head and tail, separated by a colon (:).

Example: The list [4, 3, 5] can be represented as 4 : [3, 5].
Here, 4 is the head, and [3, 5] is the tail.

Using Head and Tail in Functions (Recursion)

When defining a recursive function that processes a list, you often use pattern matching in the function argument to immediately separate the head and tail.

If you define a function sum:
sum (x:xs) = x + sum (xs)

  • If the argument is [8, 3, 2]:
    • x (the head) references 8.
    • xs (the tail) references [3, 2].

3. Essential List Operations (Haskell experience)

You must know and be able to apply the following standard list operations:

  • Return Head: Get the first element.
    Example: head [1, 2, 3] evaluates to 1.
  • Return Tail: Get the list excluding the first element.
    Example: tail [1, 2, 3] evaluates to [2, 3].
  • Test for Empty List (Null): Checks if the list is [].
    Example: null [1, 2, 3] evaluates to False.
  • Return Length: Calculates the number of elements.
    Example: length [1, 2, 3] evaluates to 3.
  • Construct Empty List: Simply [].
  • Append an Item (Concatenation): Joining two lists using ++.
    Example: [1, 2] ++ [4, 5] evaluates to [1, 2, 4, 5].
Quick Review: List Parts

Head = Single Element.
Tail = List of Elements.
Head is easy to find.
Tail takes Longer (always a list).

Key Takeaway: Lists are manipulated using HOFs and recursion, relying heavily on breaking them down into the single-element Head and the remaining list (Tail).