ruby 20 lines · 5 steps

Memoizing Fibonacci with a Hash default block

A Hash with a self-populating default block turns Fibonacci into a lazily-built, cached lookup table.

Explained by highlit
Intermediate memoization recursion hash-default lazy-evaluation
1module Fibonacci
2 CACHE = Hash.new do |cache, n|
3 cache[n] = cache[n - 1] + cache[n - 2]
4 end
5 
6 CACHE[0] = 0
7 CACHE[1] = 1
8 
9 module_function
10 
11 def [](n)
12 raise ArgumentError, "n must be non-negative" if n.negative?
13 
14 CACHE[n]
15 end
16 
17 def sequence(count)
18 Array.new(count) { |i| self[i] }
19 end
20end
01 / 01
STEP 01

Walkthrough

Space play ←→ step click any line
Three takeaways
  1. 1A Hash default block can compute and store missing values, giving you memoization for free.
  2. 2Seeding base cases up front lets a recursive default block terminate cleanly.
  3. 3Wrapping the cache behind a method lets you validate input without losing the caching benefit.

Related explainers

ruby 
require "shellwords"
require "open3"
 
module Backup

Building safe shell commands in Ruby

shell-out subprocess command-injection
Intermediate 7 steps
ruby 
class UserAgentParser
  BROWSERS = [
    [/Edg\/([\d.]+)/, "Edge"],
    [/OPR\/([\d.]+)/, "Opera"],

Parsing user-agent strings in Ruby

regex pattern-matching lookup-tables
Intermediate 8 steps
javascript 
function evaluate(expression) {
  const tokens = tokenize(expression);
  let pos = 0;
 

Building a recursive descent calculator

parsing recursion operator-precedence
Intermediate 8 steps
ruby 
class LogAggregator
  BUCKET_FORMAT = "%Y-%m-%dT%H:%M"
 
  def initialize(entries)

Bucketing log entries by the minute in Ruby

aggregation hashing enumerable
Intermediate 5 steps
ruby 
class WeeklySignupsReport
  DEFAULT_WEEKS = 12
 
  def initialize(weeks: DEFAULT_WEEKS, source: User.all)

Building a weekly signups report in Rails

service object aggregation group by
Intermediate 7 steps
rust 
use chrono::{Duration, NaiveDate};
 
#[derive(Debug)]
pub struct DateRange {

Parsing and iterating date ranges in Rust

error-handling iterators parsing
Intermediate 7 steps

Share this explainer

Here's the card — post it anywhere.

Memoizing Fibonacci with a Hash default block — share card
Made with highlit — turn any snippet into a walkthrough like this in about a minute.
Explain your code