Let’s try to prove that map id = id.

First, let’s look at map and id definitions:

map _ [] = []

map f (x:xs) = f x : map f xs

id x = x

**Base case**:

map id [] = [] = id []

**Inductive step**:

Assume that map id xs = id xs

**Prove that** map id (x:xs) = id (x:xs)

map id (x:xs) = id x : map id xs = by induction = id x : id xs = x : xs = id (x : xs)

Eta-reduction: map id = id **Q.E.D.**

Advertisements