Project 1: Immutable Todo List

Project 1: Immutable Todo List

Build a todo list application where data never changes—only new states are created.

Quick Reference

Attribute	Value
Difficulty	Beginner
Time Estimate	Weekend
Language	TypeScript
Prerequisites	Basic TypeScript, Array methods
Key Topics	Immutability, Pure Functions, State Transformations

---

1. Learning Objectives

By completing this project, you will:

1. Understand why immutability prevents entire categories of bugs
2. Learn to create new data structures instead of modifying existing ones
3. Master the spread operator and Object.freeze for enforcing immutability
4. Implement state transformations as pure functions
5. Build a foundation for understanding React’s state model
6. Learn to think about state as snapshots in time, not changing values

---

2. Theoretical Foundation

2.1 Core Concepts

What is Immutability?

Immutability means that once data is created, it cannot be changed. Instead of modifying values in place, you create new values:

// MUTABLE: The original object changes
const user = { name: "Alice", age: 30 };
user.age = 31;  // Original object modified!
console.log(user); // { name: "Alice", age: 31 }

// IMMUTABLE: A new object is created
const user1 = { name: "Alice", age: 30 };
const user2 = { ...user1, age: 31 };  // New object created
console.log(user1); // { name: "Alice", age: 30 } - unchanged!
console.log(user2); // { name: "Alice", age: 31 } - new object

Why Does Mutation Cause Bugs?

Consider this scenario in a multi-component application:

// Shared state
const todos = [
  { id: 1, text: "Buy milk", done: false }
];

// Component A marks item as done (MUTATION)
function markDone(todos: Todo[], id: number) {
  const todo = todos.find(t => t.id === id);
  if (todo) todo.done = true;  // Mutates the original!
}

// Component B is still rendering the "old" list
// but the object it references has changed underneath it!
// This causes: stale UI, race conditions, impossible debugging

With immutability:

// Component A returns a NEW list
function markDone(todos: Todo[], id: number): Todo[] {
  return todos.map(todo =>
    todo.id === id
      ? { ...todo, done: true }  // New object
      : todo
  );
}

// Component B's reference is unchanged
// Component A has a new reference
// Both can reason about their state independently

Pure Functions: The Partner of Immutability

A pure function:

1. Returns the same output for the same input (deterministic)
2. Has no side effects (doesn’t modify external state)

// IMPURE: Modifies external state
let count = 0;
function increment() {
  count++;  // Side effect!
  return count;
}
increment(); // 1
increment(); // 2 (different result!)

// PURE: No side effects
function add(a: number, b: number): number {
  return a + b;  // Always same result for same inputs
}
add(2, 3); // 5
add(2, 3); // 5 (always!)

State as Snapshots

In immutable programming, you think of state as a series of snapshots:

Time →  t0          t1          t2          t3
        ┌────┐      ┌────┐      ┌────┐      ┌────┐
state → │ [] │ ──→  │[A] │ ──→  │[A,B]│ ──→  │[B] │
        └────┘      └────┘      └────┘      └────┘
         Add A      Add B       Remove A

Each state is immutable. Transitions create NEW states.
You can keep old states for undo/redo, debugging, etc.

2.2 Why This Matters

In React and Modern Frameworks:

• React’s useState and useReducer rely on reference equality
• If you mutate state, React won’t detect the change and won’t re-render
• Redux is built entirely on immutable state updates

// React won't re-render! (mutation)
const [todos, setTodos] = useState([]);
todos.push(newTodo);  // Mutating!
setTodos(todos);      // Same reference, React ignores it

// React will re-render (immutable)
setTodos([...todos, newTodo]);  // New array reference

For Debugging:

• With mutation, state changes are invisible
• With immutability, you can log every state transition
• Time-travel debugging (Redux DevTools) becomes possible

For Concurrency:

• Immutable data is thread-safe by definition
• No locks needed because data can’t change
• Critical for web workers, async operations

2.3 Historical Context

The concept of immutability comes from mathematics and functional programming languages:

• 1958: LISP introduced immutable cons cells
• 1977: John Backus’s Turing Award lecture “Can Programming Be Liberated from the von Neumann Style?” advocated for functional approaches
• 1990s: Haskell made immutability the default
• 2013: React popularized immutability in JavaScript
• 2015: Redux made immutable state management mainstream

2.4 Common Misconceptions

“Immutability is slow because you copy everything”

• Reality: Structural sharing means you only copy what changes
• The same object references are reused when possible
• Libraries like Immer use copy-on-write for efficiency

“I need to use a special library for immutability”

• Reality: JavaScript spread operators work for most cases
• Libraries like Immer make deep updates easier but aren’t required

“Immutability means I can never change anything”

• Reality: You change state by creating new versions
• The old state still exists (until garbage collected)
• This is how React state works

---

3. Project Specification

3.1 What You Will Build

A complete todo list application with these capabilities:

• Add, toggle, and remove todos
• Filter todos by status (all, active, completed)
• Undo/redo functionality (enabled by immutability!)
• Clear completed todos
• Persist to localStorage

All operations must be implemented as pure functions that return new state.

3.2 Functional Requirements

1. Add Todo: Create a new todo with unique ID, text, and done: false
2. Toggle Todo: Toggle the done status of a todo by ID
3. Remove Todo: Remove a todo by ID
4. Filter Todos: Return todos matching a filter (all/active/completed)
5. Clear Completed: Remove all todos where done: true
6. Undo: Return to the previous state
7. Redo: Return to the next state (if available)
8. Persist: Save state to localStorage and restore on load

3.3 Non-Functional Requirements

• Immutability: No array or object mutations allowed
• Purity: All state transformations must be pure functions
• Type Safety: Full TypeScript types for state and operations
• Testability: All functions should be easily unit-testable

3.4 Example Usage / Output

// Initial state
let state: AppState = {
  todos: [],
  filter: 'all',
  history: [],
  historyIndex: -1
};

// Add a todo
state = addTodo(state, "Buy milk");
// {
//   todos: [{ id: 1, text: "Buy milk", done: false }],
//   filter: 'all',
//   history: [{ todos: [], filter: 'all' }],
//   historyIndex: 0
// }

// Add another
state = addTodo(state, "Learn FP");
// {
//   todos: [
//     { id: 1, text: "Buy milk", done: false },
//     { id: 2, text: "Learn FP", done: false }
//   ],
//   ...
// }

// Toggle first todo
state = toggleTodo(state, 1);
// {
//   todos: [
//     { id: 1, text: "Buy milk", done: true },  // Changed!
//     { id: 2, text: "Learn FP", done: false }
//   ],
//   ...
// }

// Undo
state = undo(state);
// Back to before toggle - "Buy milk" is done: false again

// Filter
const activeTodos = getFilteredTodos(state);
// Returns only todos where done: false

---

4. Solution Architecture

4.1 High-Level Design

┌─────────────────────────────────────────────────────────┐
│                      Application                         │
├─────────────────────────────────────────────────────────┤
│                                                         │
│  ┌─────────────┐    ┌─────────────┐    ┌─────────────┐ │
│  │   State     │───▶│  Reducer    │───▶│  New State  │ │
│  │  (Current)  │    │  (Pure Fn)  │    │  (Immutable)│ │
│  └─────────────┘    └─────────────┘    └─────────────┘ │
│         │                  ▲                  │         │
│         │                  │                  │         │
│         │           ┌──────┴──────┐          │         │
│         │           │   Action    │          │         │
│         │           │ (Add/Toggle │          │         │
│         │           │  /Remove)   │          │         │
│         │           └─────────────┘          │         │
│         │                                    │         │
│         ▼                                    ▼         │
│  ┌─────────────┐                    ┌─────────────┐    │
│  │   History   │◀───────────────────│  Snapshot   │    │
│  │   Stack     │                    │  (for undo) │    │
│  └─────────────┘                    └─────────────┘    │
│                                                         │
└─────────────────────────────────────────────────────────┘

4.2 Key Components

Component	Responsibility	Key Decisions
Todo type	Represents a single todo item	Readonly properties enforce immutability
AppState type	Complete application state	Includes history for undo/redo
addTodo	Creates new state with added todo	Uses spread to create new array
toggleTodo	Creates new state with toggled todo	Uses map to create new array
removeTodo	Creates new state without todo	Uses filter to create new array
undo/redo	Navigate history	Returns historical state snapshots
persist	Save/load from localStorage	Serialize/deserialize state

4.3 Data Structures

// Core todo item - all properties readonly
interface Todo {
  readonly id: number;
  readonly text: string;
  readonly done: boolean;
}

// Filter type using union types
type FilterType = 'all' | 'active' | 'completed';

// Historical snapshot for undo/redo
interface Snapshot {
  readonly todos: readonly Todo[];
  readonly filter: FilterType;
}

// Complete application state
interface AppState {
  readonly todos: readonly Todo[];
  readonly filter: FilterType;
  readonly history: readonly Snapshot[];
  readonly historyIndex: number;
  readonly nextId: number;
}

4.4 Algorithm Overview

Adding a Todo:

1. Create new todo object with next ID
2. Create new array with existing todos + new todo
3. Push current state to history
4. Return new state with updated todos and history

function addTodo(state: AppState, text: string): AppState {
  const newTodo: Todo = {
    id: state.nextId,
    text,
    done: false
  };

  return {
    ...state,
    todos: [...state.todos, newTodo],
    nextId: state.nextId + 1,
    history: [...state.history, { todos: state.todos, filter: state.filter }],
    historyIndex: state.history.length
  };
}

Undo Operation:

1. Check if historyIndex > 0
2. Get previous snapshot from history
3. Return state with snapshot’s data and decremented index

Complexity Analysis:

• Add: O(n) - copy array
• Toggle: O(n) - map over array
• Remove: O(n) - filter array
• Undo/Redo: O(1) - index lookup

---

5. Implementation Guide

5.1 Development Environment Setup

# Create project directory
mkdir immutable-todo && cd immutable-todo

# Initialize npm
npm init -y

# Install TypeScript and dev tools
npm install --save-dev typescript ts-node @types/node

# Initialize TypeScript config
npx tsc --init

# Create source directory
mkdir src

Update tsconfig.json:

{
  "compilerOptions": {
    "target": "ES2020",
    "module": "commonjs",
    "strict": true,
    "outDir": "./dist",
    "rootDir": "./src",
    "esModuleInterop": true
  }
}

5.2 Project Structure

immutable-todo/
├── src/
│   ├── types.ts        # Type definitions
│   ├── state.ts        # Initial state and state factory
│   ├── reducers.ts     # Pure state transformation functions
│   ├── selectors.ts    # Functions to query state
│   ├── persistence.ts  # localStorage save/load
│   └── index.ts        # Demo application
├── tests/
│   ├── reducers.test.ts
│   └── selectors.test.ts
├── package.json
└── tsconfig.json

5.3 Implementation Phases

Phase 1: Foundation (2-3 hours)

Goals:

• Define all TypeScript types
• Create initial state factory
• Implement basic add/toggle/remove

Tasks:

1. Create types.ts with Todo, FilterType, Snapshot, AppState
2. Use readonly on all properties to enforce immutability at type level
3. Create createInitialState() function
4. Implement addTodo using spread operator

Checkpoint: You can create state, add todos, and TypeScript prevents mutation

// This should cause a TypeScript error:
const state = createInitialState();
state.todos.push({ id: 1, text: "test", done: false }); // Error!

Phase 2: Core Functionality (3-4 hours)

Goals:

• Implement all state transformations
• Add undo/redo support
• Implement filtering

Tasks:

1. Implement toggleTodo using map
2. Implement removeTodo using filter
3. Implement clearCompleted using filter
4. Add history tracking to all operations
5. Implement undo and redo
6. Implement setFilter and getFilteredTodos

Checkpoint: All operations work, undo/redo navigates through history

Phase 3: Polish & Persistence (2-3 hours)

Goals:

• Add localStorage persistence
• Handle edge cases
• Write tests

Tasks:

1. Implement saveState and loadState with JSON serialization
2. Handle empty state, missing todos, invalid IDs
3. Write unit tests for each reducer function
4. Create a demo that shows all functionality

Checkpoint: State persists across page reloads, all tests pass

5.4 Key Implementation Decisions

Decision	Options	Recommendation	Rationale
ID Generation	UUID vs Counter	Counter	Simpler, sufficient for this project
History Storage	Full state vs Diff	Full state	Easier to implement, memory isn’t a concern
Immutability	Runtime freeze vs Type-only	Both	Types catch compile errors, freeze catches runtime errors
State Shape	Flat vs Nested	Flat	Easier to update immutably

---

6. Testing Strategy

6.1 Test Categories

Category	Purpose	Examples
Unit Tests	Test individual reducers	addTodo returns new state with todo
Property Tests	Verify immutability invariants	Original state unchanged after operation
Integration Tests	Test undo/redo sequences	Add, toggle, undo, redo restores state

6.2 Critical Test Cases

1. Immutability Guarantee: ```typescript test(‘addTodo does not mutate original state’, () => { const original = createInitialState(); const originalTodos = original.todos; const newState = addTodo(original, “test”);

expect(original.todos).toBe(originalTodos); // Same reference expect(newState.todos).not.toBe(originalTodos); // New reference });

2. **Undo Restores Previous State**:
```typescript
test('undo restores previous todos', () => {
  let state = createInitialState();
  state = addTodo(state, "first");
  const afterFirst = state;
  state = addTodo(state, "second");
  state = undo(state);

  expect(state.todos).toEqual(afterFirst.todos);
});

1. Filter Returns Correct Subset: ```typescript test(‘getFilteredTodos returns only active todos’, () => { let state = createInitialState(); state = addTodo(state, “done”); state = addTodo(state, “not done”); state = toggleTodo(state, 1); // Mark first as done state = setFilter(state, ‘active’);

const filtered = getFilteredTodos(state); expect(filtered.length).toBe(1); expect(filtered[0].text).toBe(“not done”); });

### 6.3 Test Data

```typescript
const sampleTodos: Todo[] = [
  { id: 1, text: "Buy milk", done: false },
  { id: 2, text: "Learn FP", done: true },
  { id: 3, text: "Build project", done: false }
];

const sampleState: AppState = {
  todos: sampleTodos,
  filter: 'all',
  history: [],
  historyIndex: -1,
  nextId: 4
};

---

7. Common Pitfalls & Debugging

7.1 Frequent Mistakes

Pitfall	Symptom	Solution
Mutating with push/splice	Tests pass but React doesn’t re-render	Use spread: [...arr, item]
Forgetting to copy nested objects	Parent changes but child doesn’t	Deep spread: { ...obj, nested: { ...obj.nested, prop: val } }
Not updating history on every operation	Undo doesn’t work for some actions	Add history push to every reducer
Modifying state inside map/filter callback	Subtle bugs, inconsistent state	Return new objects from callbacks
Using const and thinking it’s immutable	Object properties still changeable	Use Object.freeze() or readonly types

7.2 Debugging Strategies

• Log Before/After: Print state before and after each operation
• Reference Equality Check: Use === to verify new objects created
• Object.freeze(): Freeze state in development to catch mutations
• TypeScript Readonly: Let the compiler catch mutation attempts

// Development-only freeze helper
function deepFreeze<T>(obj: T): T {
  if (process.env.NODE_ENV === 'development') {
    return Object.freeze(
      Object.keys(obj).reduce((acc, key) => {
        const val = (obj as any)[key];
        (acc as any)[key] = typeof val === 'object' ? deepFreeze(val) : val;
        return acc;
      }, {} as T)
    );
  }
  return obj;
}

7.3 Performance Traps

• Copying Large Arrays: For huge lists, consider structural sharing libraries (Immer, Immutable.js)
• History Memory: Limit history length to prevent memory issues
• Selector Memoization: Memoize getFilteredTodos to avoid recalculation

---

8. Extensions & Challenges

8.1 Beginner Extensions

• Due Dates: Add optional due date to todos, sort by due date
• Categories: Add categories/tags to todos, filter by category
• Priority Levels: Add priority (high/medium/low), sort by priority

8.2 Intermediate Extensions

• Drag and Drop Reorder: Reorder todos while maintaining immutability
• Batch Operations: Mark multiple todos done at once
• Search: Filter todos by text search

8.3 Advanced Extensions

• Structural Sharing: Implement your own structural sharing for arrays
• Time Travel UI: Build a UI that shows all history states
• Conflict Resolution: Handle concurrent edits to the same todo

---

9. Real-World Connections

9.1 Industry Applications

• React’s useState/useReducer: Built entirely on immutable state updates
• Redux: The most popular state management library, requires immutability
• Git: Commits are immutable snapshots with references to parent states
• Event Sourcing: Database pattern where events are immutable

9.2 Related Open Source Projects

• Immer: https://github.com/immerjs/immer - Write mutable code that produces immutable updates
• Immutable.js: https://github.com/immutable-js/immutable-js - Persistent immutable collections
• Redux: https://github.com/reduxjs/redux - Predictable state container

9.3 Interview Relevance

• “Explain why React needs immutability”: Direct application of this project
• “How would you implement undo/redo?”: History management pattern
• “What’s the difference between mutation and immutability?”: Core concept

---

10. Resources

10.1 Essential Reading

• “Functional-Light JavaScript” by Kyle Simpson - Chapter 6: Value Immutability
• “Hands-On Functional Programming with TypeScript” by Remo Jansen - Chapter 2
• React docs on Updating Arrays in State: https://react.dev/learn/updating-arrays-in-state

10.2 Video Resources

• “Immutability in JavaScript” - Fun Fun Function (YouTube)
• “Redux in 100 Seconds” - Fireship (YouTube)

10.3 Tools & Documentation

• TypeScript Readonly: https://www.typescriptlang.org/docs/handbook/2/objects.html#readonly-properties
• MDN Spread Syntax: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Spread_syntax

10.4 Related Projects in This Series

• Next Project: P02 - Pipe Text Processor - Function composition
• Future Project: P03 - Maybe Monad - Uses immutability for containers

---

11. Self-Assessment Checklist

Before considering this project complete, verify:

Understanding

• I can explain why arr.push(x) is mutation and [...arr, x] is not
• I can explain why React needs immutability for re-rendering
• I understand the difference between value equality and reference equality
• I can explain how undo/redo is enabled by immutability

Implementation

• All reducers return new state objects
• TypeScript readonly modifier prevents mutations at compile time
• All test cases pass
• Undo/redo works correctly for all operations
• State persists to localStorage

Growth

• I’ve identified patterns I’ll use in my React applications
• I can spot mutation bugs in code reviews
• I understand the tradeoffs of immutability (memory vs safety)

---

12. Submission / Completion Criteria

Minimum Viable Completion:

• All CRUD operations implemented immutably
• TypeScript compiles with no errors
• At least 5 unit tests passing
• Demo script shows all functionality

Full Completion:

• Undo/redo fully functional
• localStorage persistence working
• Comprehensive test coverage (>80%)
• No mutations detected with Object.freeze()

Excellence (Going Above & Beyond):

• Time travel UI to visualize history
• Performance optimizations for large lists
• Integrated with a real React application

---

This guide was generated from FUNCTIONAL_PROGRAMMING_TYPESCRIPT_LEARNING_PROJECTS.md. For the complete learning path, see the parent directory.