Short Pieces, Efficiently Joined

Nalbinding is the awkward older cousin of knitting. Instead of working from one continuous strand, you join short lengths of yarn — maybe 50cm at a time — splicing a fresh piece whenever the working thread runs out. It looks inefficient until you’ve done it for an evening and notice that you never have to drag a kilometre of wool through every loop. You only ever handle the short piece in your hand.

Ropes solve the same problem for text. A naive string is one contiguous buffer, so inserting a character in the middle of a megabyte means copying the whole megabyte. A rope stores the text as a binary tree whose leaves are short strings, and whose internal nodes just record how long their left subtree is. Concatenation becomes a single new node; you never copy the underlying characters. The structure dates to a 1995 paper by Boehm, Atkinson, and Plass, and it still lives inside text editors that have to stay responsive on huge files.

In Go, a leaf holds a string and an internal node holds two children plus a weight — the length of everything to its left:

package main

import (
	"fmt"
	"strings"
)

type Rope struct {
	left, right *Rope
	str         string
	weight      int // total length of the left subtree
}

func leaf(s string) *Rope { return &Rope{str: s} }

func concat(l, r *Rope) *Rope {
	return &Rope{left: l, right: r, weight: l.length()}
}

func (n *Rope) length() int {
	if n.left == nil && n.right == nil {
		return len(n.str)
	}
	return n.left.length() + n.right.length()
}

func (n *Rope) index(i int) byte {
	if n.left == nil && n.right == nil {
		return n.str[i]
	}
	if i < n.weight {
		return n.left.index(i)
	}
	return n.right.index(i - n.weight)
}

func (n *Rope) String() string {
	if n.left == nil && n.right == nil {
		return n.str
	}
	var b strings.Builder
	b.WriteString(n.left.String())
	b.WriteString(n.right.String())
	return b.String()
}

func main() {
	r := concat(concat(leaf("nal"), leaf("bind")), leaf("ing"))
	fmt.Println(r.String())
	fmt.Printf("len=%d char4=%c\n", r.length(), r.index(4))
}

The weight is what makes indexing fast. To find character 4, I check the root’s weight: if the index is smaller, descend left; otherwise subtract the weight and descend right. No buffer is ever scanned linearly — the tree routes the lookup in time proportional to its depth. Three short leaves, "nal", "bind", and "ing", present themselves as the single word nalbinding, and index(4) returns i without ever flattening the tree.

Lua expresses the same shape with tables, using 1-based indexing the way Lua prefers:

local function leaf(s)
  return { str = s }
end

local function len(node)
  if node.str then return #node.str end
  return len(node.left) + len(node.right)
end

local function concat(l, r)
  return { left = l, right = r, weight = len(l) }
end

local function index(node, i) -- 1-based
  if node.str then return node.str:sub(i, i) end
  if i <= node.weight then return index(node.left, i) end
  return index(node.right, i - node.weight)
end

local function flatten(node)
  if node.str then return node.str end
  return flatten(node.left) .. flatten(node.right)
end

local r = concat(concat(leaf("nal"), leaf("bind")), leaf("ing"))
print(flatten(r))
print(string.format("len=%d char5=%s", len(r), index(r, 5)))

Both print nalbinding and then locate a single character by walking weights instead of scanning bytes. The Go version’s char4 and the Lua version’s char5 are the same letter — the gap is only the off-by-one between zero- and one-based indexing — and both land on i.

The connection that keeps me coming back to it: in both the wool and the tree, the win is that you never touch the whole thing at once. Nalbinding splices a new 50cm length and the finished fabric grows; a rope hangs a new leaf off a node and the document grows. The full object is a fiction assembled from short pieces you can actually hold.