Lists & Recursion: The Snake's Body

A snake is just a list of cells with the head at the front — and every classic snake move turns out to be a tiny function on that list.

You will be able to…

Build lists with [] and ::, and read types like (int * int) list
Write recursive functions that follow a list's shape
Grow a snake, measure it, and detect self-collision
Reach for List.map, List.mem and List.fold_left when the stdlib already did the work

The body plan

Our snake lives on a grid, so each body segment is a cell — an (x, y) pair of ints, a tuple doing exactly the fleeting job lesson 2.1 promised. The whole body is a list of cells, head first. That convention matters: the head is where everything happens, so it sits where lists are fast — the front.

Three tools in one screenful. Square brackets with semicolons build a list literal. The cons operator :: puts one element in front of a list — instantly, without touching the old list: after bigger is born, body still has three cells. (There's also @, which glues two whole lists together — handier but slower: it walks everything on its left.) And List.map makes a new list by applying a function to every element — here sliding the whole body one cell east. Old body untouched, of course. The immutability law from lesson 2.1 holds for lists too, and it will pay off shortly.

Write grow : int * int -> (int * int) list -> (int * int) list: the new head cell goes in front of the body. One operator, no recursion required.

Which operator puts one element in front of a list?

new_head :: body — that's the whole function.

Recursion: follow the shape

Here is the secret that unlocks every list function ever written. A list is one of exactly two things: the empty list [], or a first element consed onto a rest — the pattern cell :: rest. Two shapes… and you just spent a lesson learning the tool for "one of exactly two things": match! A recursive function answers the easy shape directly, and for the other shape does a little work plus a call to itself on the rest. The rest is always shorter, so the journey always reaches [] and stops. Watch len measure a body:

len [ (5,5); (4,5) ]
= 1 + len [ (4,5) ]
= 1 + (1 + len [])
= 1 + (1 + 0)
= 2

Write len yourself, with let rec and a match on the two shapes. No peeking at the standard library — the point is to feel the pattern in your fingers.

The _ means "there's a first element but I don't need its value" — only its existence counts.

Second arm: 1 + len rest. The recursion does the walking for you.

Confession time: the stdlib already ships List.length, and what you just wrote is essentially its source code. That's the deal in this lesson — you build a few classics by hand to own the pattern, then you're allowed to be lazy forever.

ℹ️ The List module is your armoury: List.length, List.map, List.mem, List.filter, List.fold_left, List.rev… When a loop itch strikes, check the armoury first.

Break it on purpose: one list, one type

A list holds elements of a single type — (int * int) list means pairs all the way down. Sneak a bare int in and see exactly where the armour plate deflects it:

The error points at the 3: it has type int but was expected to have type int * int. The first elements set the standard; everything after must match it. A snake made of cells can't secretly contain a loose number — one more bug species extinct at compile time.

Self-collision: is that cell already snake?

The classic snake death: the head lands on a cell the body already occupies. As a function, that's just "does this list contain this cell?". You can write the recursion yourself — [] contains nothing; c :: rest contains the cell if c is it, or if rest contains it — or you can use the armoury's List.mem : 'a -> 'a list -> bool. The tests only care about behaviour. Your call.

Write contains : int * int -> (int * int) list -> bool — true exactly when the cell appears somewhere in the body.

Pairs compare with plain =, and || means "or".

c = cell || contains cell rest — found here, or found later.

Shortcut of champions: let contains cell body = List.mem cell body.

The tail must go

Think about how a snake actually slithers: a new head cell appears in front, and the last tail cell vanishes. Growth is grow; moving is grow plus dropping the last cell. That second half is today's boss fight, and it needs three shapes, because "the last element" is really "the list with exactly one element left" — the pattern [ _ ].

⚠️ Runtime traps live at the ends of lists: List.hd [] doesn't return a polite None — it raises an exception and crashes the game. Pattern matching (or the option-returning cousins like List.nth_opt) keeps you honest about the empty case. Our tests always poke the empty and one-cell snakes — so should yours.

Write drop_last : (int * int) list -> (int * int) list — a copy of the body without its final cell. The empty body stays empty; a one-cell body becomes empty; otherwise keep the head and recurse on the rest.

[ _ ] matches exactly a one-element list — that lone element is the last one, so it goes.

Third arm: keep the cell, cons it onto whatever dropping the last of rest gives you.

cell :: drop_last rest. Skip the [ _ ] arm and the last cell never gets dropped — an immortal, ever-growing tail.

🧠 Coach's corner — this is structural recursion: the function's shape mirrors the type's shape, and each call recurses on something strictly smaller, so termination is free. Have Maks hand-trace drop_last [ (5,5); (4,5); (3,5) ] on paper like the len trace above — writing the nested cell :: (…) expansions out is the moment it clicks. Then ask the killer question: "why does the [ _ ] arm have to come before cell :: rest?" (Because match tries arms in order, and a one-element list fits both patterns.)

Bonus loot: folding a whole list into one value

Map transforms every element; filter keeps the ones passing a test; fold crunches a whole list down to a single value — the score counter's best friend. List.fold_left f start lst starts from start and feeds it through f with each element in turn:

Quick one: write total : int list -> int, the sum of a list of coin values, using List.fold_left.

The accumulator starts at 0; each coin adds itself: acc + c.

🎮 Side quest: in any Run box, build your party roster — let party = [ "Maks"; "Alexandre"; "Grumbletooth" ] — then List.map (fun n -> "Sir " ^ n) party to knight everyone, and a fold to find the longest name (String.length + max). Trumpet fanfare optional.

Checkpoint quiz

Loot collected

A snake body is (int * int) list, head first; :: grows it at the front in constant time.
Every list is [] or cell :: rest — recursive functions match those two shapes (plus [ _ ] when the last element is special).
grow, len, contains, drop_last: the entire snake anatomy, as pure functions.
The armoury: List.length, List.map, List.mem, List.filter, List.fold_left.
Old lists never change — consing and mapping build new ones.

Next: the heartbeat. One pure function, called sixty times a second — the tick.