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 "csv"
 
class SalesReport
  def initialize(path)

Aggregating CSV sales data in Ruby

data-aggregation memoization group_by
Intermediate 6 steps
python 
from collections.abc import Mapping
from typing import Any, Iterator
 
 

Flattening nested config into dotted keys

recursion generators tree-traversal
Intermediate 7 steps
ruby 
module DurationFormatter
  UNITS = [
    ['week', 604_800],
    ['day', 86_400],

Turning seconds into human-readable durations in Ruby

greedy-decomposition modular-arithmetic formatting
Intermediate 7 steps
ruby 
class Comment < ApplicationRecord
  belongs_to :post
  belongs_to :author, class_name: "User"
 

Live-updating comments with Turbo in Rails

turbo-streams callbacks associations
Intermediate 8 steps
ruby 
require 'json'
require 'set'
 
class SensitiveScrubber

Recursively scrubbing secrets from JSON

recursion data-masking pattern-matching
Intermediate 7 steps
rust 
use std::collections::HashMap;
 
pub struct Memoizer<K, V, F> {
    cache: HashMap<K, V>,

A generic memoizer in Rust

memoization generics caching
Intermediate 6 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