Skip to main content

Code Katas

Short, repeatable drills. 20-40 minutes each. The point of a kata is fluency, not novelty -- do each one cold, from scratch, at least twice, across the week.

Kata 1: map, filter, reduce in C​

Skill targeted: programming HOFs in a language that does not natively give them; function-pointer discipline.

Instructions:

Implement:

typedef void* (*map_fn)(void *x, void *ctx);
typedef int   (*pred_fn)(void *x, void *ctx);
typedef void* (*fold_fn)(void *acc, void *x, void *ctx);

void** map_list   (void **xs, size_t n, map_fn f, void *ctx);
void** filter_list(void **xs, size_t n, pred_fn p, void *ctx, size_t *out_n);
void*  reduce_list(void **xs, size_t n, void *init, fold_fn f, void *ctx);

Write a small main that uses all three on an array of ints (boxed as int*) to compute the sum of squares of the odd numbers in [1..10]. Note the ctx parameter -- the only way to pass "captured state" without closures.

Time limit: 30 minutes.

Kata 2: map, filter, reduce in Scheme​

Skill targeted: implementing the canonical HOFs from first principles.

Instructions:

Do not use library versions. Write:

(define (map f xs) ...)
(define (filter p xs) ...)
(define (reduce f init xs) ...)

Use them to express:

  • the sum of 1^2 + 2^2 + ... + 10^2
  • the list of strings that are longer than 3 characters
  • the product of all even numbers in [2..20]

Extension: write accumulate such that map, filter, reduce can all be expressed in terms of it in one line each.

Time limit: 20 minutes.

Kata 3: Tiny eval / apply Interpreter​

Skill targeted: writing a minimum-viable evaluator from memory.

Instructions:

Implement, from a blank file, a Python (or C) evaluator that supports:

  • numbers, symbols
  • quote, if, define, lambda
  • procedure application
  • primitives: +, -, *, =

Target: under 40 lines of Python for the core eval + apply, not counting the tokenizer. Correctness only: no extensions, no error messages. Must pass (define fact (lambda (n) (if (= n 0) 1 (* n (fact (- n 1)))))) (fact 6) ; => 720.

Do this kata at least three times in the week. It should eventually feel routine.

Time limit: 40 minutes (first pass), 20 minutes (third pass).

Kata 4: Tail-Call Iteration​

Skill targeted: writing tail-recursive procedures; recognizing recursive-process vs iterative-process.

Instructions:

Write each both ways -- recursive-process and tail-recursive -- in Scheme. Use a helper with an accumulator for the tail-recursive version. Label each answer with the space complexity.

  • (sum-list xs) -- sum of a list of numbers
  • (length xs) -- length of a list
  • (reverse xs) -- reverse a list
  • (power b n) -- b^n

Then in Python, attempt to write sum-list tail-recursively and run it on a 10 000-element list. Describe what fails and why. Rewrite as a loop.

Time limit: 25 minutes.

Kata 5: Closure Traps​

Skill targeted: diagnosing classic closure bugs.

Instructions:

Run (or mentally run) each snippet. Predict the output before running. If wrong, diagnose.

a. Python loop capture​

fs = [lambda: i for i in range(3)]
print([f() for f in fs])

b. Shared state in a class-like closure​

(define (make-pair)
  (let ((x 0))
    (cons (lambda () (set! x (+ x 1)) x)
          (lambda () x))))
(define p (make-pair))
((car p)) ((car p)) ((cdr p))

c. Fake dynamic scope​

(define n 5)
(define f (lambda () n))
(let ((n 99)) (f))

For each, write one sentence explaining what the evaluation model says.

Time limit: 15 minutes.

Kata 6: Stream / Generator Pipelines​

Skill targeted: laziness and pipeline composition.

Instructions:

In Python (generators) or Scheme (cons-stream/stream-car/stream-cdr):

  • Build the stream of odd naturals.
  • Transform with stream-map to squares.
  • Filter with stream-filter to those greater than 50.
  • Take the first 5.

Then do it all in a single expression without intermediate variables. Finally, confirm (by inserting a print in the map step) that only ~9-10 values are ever materialized.

Time limit: 20 minutes.

Evidence Check​

  • All six katas attempted at least once.
  • Katas 1 and 3 attempted at least twice each.
  • A log with predicted vs actual outputs for Kata 5.
  • Kata 3 (tiny interpreter) reached "under 40 lines" at least once.