Lists in functional programming

Welcome to the World of Functional Lists!

Hello! Today we are going to explore Lists, but not quite in the way you might have seen them in Python or Java. In Functional Programming, lists are the most important way to store data.

Don't worry if this seems a bit "mathematical" or strange at first. In procedural programming, we tell the computer how to do things step-by-step. In functional programming, we describe what things are. Understanding lists is the key to mastering this new way of thinking!

1. What is a Functional List?

In functional programming, a list is a collection of elements of the same data type. However, unlike a standard array, a functional list is recursive. This means a list is defined in terms of itself!

A list is always one of two things:
1. An Empty List (usually shown as \( [ ] \)).
2. A Head (the first element) attached to a Tail (which is itself another list).

The "Train" Analogy

Imagine a toy train.
- The Head is the engine at the very front.
- The Tail is every other carriage coupled behind it.
- If you uncouple the engine, the remaining carriages still look like a shorter train! Eventually, if you keep uncoupling, you are left with nothing—the Empty List.

Quick Review: Every non-empty list has exactly one head and one tail (even if the tail is just an empty list).

2. The Head and the Tail

These are the two fundamental "parts" of any list you will work with in the 9645 syllabus.

The Head

The Head is the first element of the list. It is a single item (like an Integer or a Character).
Example: In the list \( [5, 8, 2, 1] \), the Head is \( 5 \).

The Tail

The Tail is everything else in the list after the head. Crucially, the tail is always a list itself.
Example: In the list \( [5, 8, 2, 1] \), the Tail is \( [8, 2, 1] \).

Memory Aid: The "H" and "T" Trick

- Head is the Hat (on top/at the front).
- Tail is the Train (everything following behind).

3. List Notation and Construction

In your exam, you might see lists written in a few ways. The most common is using the Cons operator (short for "construct").

The Cons Operator \( (:) \) or \( (|) \)

We use this to stick a Head onto a Tail to make a new list.
The syntax usually looks like this: \( Head : Tail \).

Example Walkthrough:
How do we build the list \( [10, 20, 30] \)?
1. Start with the empty list: \( [ ] \)
2. Add 30 to it: \( 30 : [ ] \) which becomes \( [30] \)
3. Add 20 to that: \( 20 : [30] \) which becomes \( [20, 30] \)
4. Add 10 to that: \( 10 : [20, 30] \) which becomes \( [10, 20, 30] \)

Common Mistake to Avoid: Students often think the tail of \( [5] \) is nothing. Actually, the tail of \( [5] \) is the empty list \( [ ] \). Remember: The tail must always be a list!

4. Operations on Lists

Because functional programming doesn't use "loops" (like for or while), we use these list properties to process data.

Is the List Empty?

Functional languages have a built-in way to check if a list is \( [ ] \). This is vital because it tells our functions when to stop (the base case).

Extracting Values

We use pattern matching to take a list apart.
If we have a list \( L = [x : xs] \):
- \( x \) represents the Head.
- \( xs \) represents the Tail (the 's' stands for 'plural', as in 'more x's').

Key Takeaway:
\( Head([1, 2, 3]) = 1 \)
\( Tail([1, 2, 3]) = [2, 3] \)

5. Why use Lists in Functional Programming?

Did you know? In functional programming, lists are immutable. This means once a list is created, it cannot be changed. If you want to "add" an item, you actually create a brand new list by "consing" a new head onto the old list.

This makes programs much more predictable and helps prevent bugs where data changes unexpectedly!

Summary Checklist

Before you move on, make sure you can:
- Identify the Head of any list (it's an element).
- Identify the Tail of any list (it's a list).
- Explain that an empty list is represented as \( [ ] \).
- Understand that \( 1 : [2, 3] \) is the same as \( [1, 2, 3] \).
- Recognize that the tail of a single-item list is the empty list.

Don't worry if this feels a bit abstract! The more you practice "splitting" and "joining" these lists, the more natural it will feel. You're doing great!