Writing functional programs

Welcome to Functional Programming!

In this chapter, we are going to explore a different way of telling computers what to do. Most of the programming you have done so far is likely Imperative—telling the computer a list of step-by-step instructions. Functional Programming is different! It’s like using a set of mathematical formulas to transform data into what you want.

Don’t worry if this feels a bit like "maths class" at first. Once you see the patterns, you’ll realize it is a very clean and powerful way to write code that has fewer bugs!

1. Functional vs. Imperative Programming

To understand functional programming, we first need to look at what it *isn't*.

• Imperative Programming: You tell the computer how to do something by changing the state of the program (using variables that change value over time). Analogy: A recipe where you change the state of the ingredients (chop the onions, fry the beef).
• Functional Programming: This is Declarative. You tell the computer what you want by applying functions. You don't change the data; you create new data. Analogy: A mathematical formula like \( f(x) = x + 2 \). If \( x \) is 5, the answer is always 7. It doesn't change the 5; it just gives you a 7.

Key Features of Functional Programming

Statelessness: In functional programming, we avoid changing the "state." This means we don't use global variables that change value as the program runs.
Side-Effect Free: A function should only do one thing: take an input and return an output. It shouldn't "reach out" and change anything else, like printing to a screen or updating a database.
Referential Transparency: This is a fancy way of saying that if you call a function with the same input, you will always get the same output. It’s predictable and reliable!

Quick Review Box:
• Imperative: Tells the computer how (step-by-step, changing variables).
• Functional: Tells the computer what (using functions, no side effects).
• Referential Transparency: Same input = Same output, every single time.

2. Functions as First-Class Objects

In languages like Haskell or Python (when used functionally), functions are treated as First-Class Objects. This means you can treat a function just like any other piece of data, such as an integer or a string.

You can:
1. Pass a function as an argument to another function.
2. Return a function as the result of another function.
3. Assign a function to a variable.

Analogy: Think of a function like a "tool." In procedural programming, tools are locked in a shed. In functional programming, you can put a tool inside a box, give it to a friend, or even have one tool build another tool!

Key Takeaway: If you can treat a function like a variable, it is a First-Class Object.

3. Function Application

In functional programming, we use Function Application. This is simply the process of giving a function its arguments so it can produce a result.

We usually write this as \( f \, x \), where \( f \) is the function and \( x \) is the argument.
Example: If we have a function called square, then square 5 would result in 25.

Did you know? In functional languages, we often don't use brackets for function calls! Instead of square(5), we just write square 5.

4. Higher-Order Functions

This is where things get exciting! A Higher-Order Function is a function that takes another function as an argument, or returns a function as its result. You need to know three main ones for your syllabus:

A. Map

Map takes a function and a list. It applies that function to every single item in the list and returns a new list.
Example: Use map with a "Double" function on the list [1, 2, 3] to get [2, 4, 6].

B. Filter

Filter takes a condition (a function that returns True or False) and a list. It looks at every item and only keeps the ones that meet the condition.
Example: Use filter with an "IsEven" function on [1, 2, 3, 4] to get [2, 4].

C. Reduce (or Fold)

Reduce takes a list and "shrinks" it down to a single value by applying a function repeatedly.
Example: Use reduce with an "Addition" function on [1, 2, 3, 4] to get 10 (because 1+2+3+4 = 10).

Memory Aid: The Kitchen Analogy
• Map: Chopping *all* the vegetables in a basket.
• Filter: Picking only the *ripe* tomatoes from the basket.
• Reduce: Throwing all the vegetables into a pot to make *one* soup.

5. Working with Lists

In functional programming, lists are very important. We usually break them down into three parts:

1. Head: The very first element in the list.
2. Tail: A list containing everything else except the head.
3. Empty List: A list with nothing in it, often shown as [ ].

Example: In the list [10, 20, 30, 40]:
• The Head is 10.
• The Tail is [20, 30, 40].

Common Mistake: Students often think the "Tail" is just the last item (40). It isn't! The Tail is the rest of the list. If you take the head of the tail [20, 30, 40], you get 20!

Key Takeaway: Every non-empty list has a head (an item) and a tail (another list).

Summary and Tips

• Functional programming is declarative and avoids side effects.
• First-class objects mean functions can be passed around like data.
• Higher-order functions (Map, Filter, Reduce) make processing lists very easy.
• Lists are made of a head and a tail.

Exam Tip: If a question asks why functional programming is useful for multi-core processors, remember: because there are no side effects and no shared state, different parts of the program can run on different cores at the same time without interfering with each other!