Building Solutions One Star at a Time

Watching stars emerge through a long-exposure lens teaches patience—each photon arrives precisely when needed, building an image gradually. Lazy evaluation works the same way, computing values only when demanded, like a knight’s tour that explores paths only as far as necessary.

In Haskell, this patience is built into the language’s DNA:

inBounds :: (Int, Int) -> Bool
inBounds (x, y) = x >= 0 && x < 8 && y >= 0 && y < 8

knightMoves :: (Int, Int) -> [(Int, Int)]
knightMoves (x, y) = [(x+dx, y+dy) | dx <- [-2,-1,1,2], dy <- [-2,-1,1,2], 
                      abs dx + abs dy == 3, inBounds (x+dx, y+dy)]

tour :: [(Int, Int)] -> [[(Int, Int)]]
tour path = path : concat [tour (move : path) | move <- validMoves, move `notElem` path]
  where validMoves = knightMoves (head path)

The beauty here? tour generates a vast tree of possibilities, but Haskell only evaluates branches as you traverse them. Like stacking star exposures, each computation happens precisely when light reaches the sensor.

Rust achieves similar laziness through iterators, though more explicitly:

fn in_bounds((x, y): (i8, i8)) -> bool {
    (0..8).contains(&x) && (0..8).contains(&y)
}

fn knight_moves((x, y): (i8, i8)) -> impl Iterator<Item = (i8, i8)> {
    const DELTAS: [(i8, i8); 8] = [
        (-2, -1), (-2, 1), (-1, -2), (-1, 2),
        (1, -2), (1, 2), (2, -1), (2, 1),
    ];
    DELTAS.into_iter()
        .map(move |(dx, dy)| (x + dx, y + dy))
        .filter(|&pos| in_bounds(pos))
}

fn knight_paths(start: (i8, i8)) -> impl Iterator<Item = Vec<(i8, i8)>> {
    std::iter::once(vec![start])
        .flat_map(|path| knight_moves(*path.last().unwrap())
            .filter_map(move |pos| {
                if path.contains(&pos) {
                    None
                } else {
                    let mut next = path.clone();
                    next.push(pos);
                    Some(next)
                }
            }))
}

Rust’s iterators are pull-based—like manually advancing film between exposures. Each .next() call reveals another stellar pathway, but only when requested.

Both approaches mirror the photographer’s art: whether capturing light over hours or exploring chess squares, the most elegant solutions reveal themselves gradually, one careful step illuminating the next.