What Is a Step Function Dictionary and How Does `s#` Enable It?

Question

What happens when you apply the sorted attribute to a dictionary's key list? What useful behaviour does this enable?

Solution

/ Standard dictionary — exact key lookup only
d: 10 20 30 40 50 ! `a`b`c`d`e
d 20             / `b — exact match
d 19             / ` — no key 19, returns null

/ Sorted dictionary (step function) — returns value for largest key ≤ query
d: `s# 10 20 30 40 50 ! `a`b`c`d`e

d 20             / `b — exact match (same as before)
d 19             / `a — largest key ≤ 19 is 10, returns `a
d 35             / `c — largest key ≤ 35 is 30, returns `c
d 5              / `  — no key ≤ 5, returns null (generic null)
d 10000          / `e — largest key ≤ 10000 is 50, returns `e

/ Keys must be sorted — unsorted throws 's-fail
`s# 20 10 30 40 50 ! `a`b`c`d`e    / 's-fail

Explanation

A standard q dictionary performs exact key lookup: if the key exists, return its value; if not, return null. This is the default behaviour for any dictionary regardless of its key type.

When the key list has the s# (sorted) attribute applied, the dictionary becomes a step function: looking up a key that does not exist returns the value associated with the largest key that is less than or equal to the query value. The result "steps" from one value to the next at each key boundary.

Why this is useful:

Step functions are the natural data structure for representing state that changes at known points in time and stays constant between those points:

/ Exchange rate: changes at known timestamps, held constant between them
fxRates: `s# 09:00:00 10:30:00 13:00:00 ! 1.25 1.27 1.24

fxRates 09:15:00   / 1.25 — rate at 09:00 still applies
fxRates 10:30:00   / 1.27 — exact match
fxRates 11:45:00   / 1.27 — rate at 10:30 still applies
fxRates 13:30:00   / 1.24 — rate at 13:00 still applies

/ Instrument status changes
status: `s# 09:00:00 09:35:00 10:15:00 ! `open`halted`open

status 09:20:00    / `open
status 09:40:00    / `halted
status 10:30:00    / `open

This pattern is also how kdb+'s as-of join (aj) works internally — it finds the value at the largest key ≤ the query time. A sorted dictionary provides the same semantics in a lightweight, explicit form.

The keys must be in ascending order for s# to apply. Any lookup on a step function relies on binary search; if the keys are not actually sorted, the results will be incorrect. kdb+ enforces this at apply time — `s# throws 's-fail if the keys are not in ascending order.