mu 0.5¶

mu is a small language for LeetCode. mu/mu.py transpiles a mu file to Python that LeetCode accepts: one class Solution, the imports it needs, and the source of every helper it calls. This document describes version 0.5. Earlier versions: 0.1, 0.2, 0.3, 0.4.

Changes since 0.4¶

A loop may name no variable: for 0..<n runs its body n times.
A lambda may be the value of an assignment: add = (a, b) -> a + b.
A new helper, heap, is a min-heap or a max-heap. <- pushes onto it and . pops from it, as on a list.
ret res = ... names the return value of a def.
A target of = may be wrapped in a function: int(a), b = s.split ':' converts a.

An example¶

# 1792. Maximum Average Pass Ratio
def maxAverageRatio(classes: [[int]], extraStudents: int) -> float
  gain = (p, t) -> (p + 1) / (t + 1) - p / t
  h = heap([(gain(p, t), p, t) for (p, t) in classes], type=max)
  for 0..<extraStudents
    _, p, t = h .
    h <- (gain(p + 1, t + 1), p + 1, t + 1)
  (sum for (_, p, t) in h: p / t) / len(classes)

Running¶

python mu/mu.py file.mu        # print the Python
python mu/mu.py --fmt file.mu  # print the file, formatted
python mu/mu.py -              # read from standard input

Lexical structure¶

Blocks are marked by indentation, as in Python. There is no colon at the end of a block header.
A line inside open brackets continues onto the next line.
Comments start with #.
Strings are Python strings: single or double quotes, triple quotes, and the prefixes f, r and b.
true, false and none are True, False and None. inf is math.inf and imports it.

Program structure¶

A file has five parts, in this order. Each part is optional.

Imports, written as in Python: import a.b, from a import b, c.
extends Base, which makes the class class Solution(Base).
Top-level assignments before the first def. They become module-level Python, above the class.
The defs. Each one becomes a method of Solution; self is added.
A script: every statement after the defs. It runs after the class. A def in the script is a plain function, not a method.

Functions¶

def name(p: T, q: U) -> R
  body

The last line of a body is its return value. If the last statement is an if, the last line of each arm is returned. return also works.

A nested def that assigns a name bound by an enclosing def gets a nonlocal declaration automatically.

A line of the body may start with ret. It assigns a variable, and that variable is the return value: the function returns it after its last line, and a bare return returns it too. A return with a value still returns that value. In ret res, k = [], 0 the first name, res, is the return value. A body has at most one ret line, and it cannot be inside a loop or an if.

# 1720. Decode XORed Array
def decode(encoded: [int], first: int) -> [int]
  ret res = [first]
  for i in range len encoded
    res <- encoded[i] ^ res[i]

ret is a keyword only at the start of a line and before name = or name,. Anywhere else it is an ordinary name, so ret = 0 is a plain assignment.

Types¶

[T]          # list[T]
{T}          # set[T]
{K: V}       # dict[K, V]
(A, B)       # tuple[A, B]
T?           # Optional[T]
A -> B       # Callable[[A], B]
(A, B) -> C  # Callable[[A, B], C]
char         # str
none         # None

Any other name passes through unchanged.

Grid parameters¶

A parameter of a top-level def whose type is [[T]] is wrapped in Grid. A Grid takes a cell pair as one index: mat[p] is mat[i][j] when p = (i, j), for reading and for writing. Only such parameters are wrapped. A table built inside the function, for example with like, is a plain list of lists.

Statements¶

Loops¶

for x in xs       # x is each item
for (a, b) in ps  # unpacks each pair
for i, x in xs    # enumerate: i is the index, x the item
for xs            # runs once per item of xs, names no variable
for 0..<n         # so this runs n times
while cond        # as in Python

A loop may end with an else block, which runs when the loop finishes without break, as in Python.

for a, b in xs without brackets always means enumerate(xs). To unpack pairs, write the brackets.

A for with no in compiles to for _ in xs.

Push and pop¶

stack <- x  # stack.append(x)
stack .     # stack.pop()

Both work on a heap too, because a heap has an append method that pushes.

A . followed by a name is attribute access. A . followed by anything else is a pop.

Assignment¶

Python assignment and every augmented operator (+=, //=, <<=, ...). Chained assignment a = b = 0 works.

A target of = may be wrapped in a one-argument function. The name is assigned, then passed through the function:

int(id), ev, int(t) = log.split ':'

compiles to

id, ev, t = log.split(':')
id, t = int(id), int(t)

With "0:start:3", id is 0, ev is "start" and t is 3.

Other statements¶

if/elif/else, break, continue, pass, del, assert, return, as in Python.

Expressions¶

Python expressions, with these additions.

Calls without brackets¶

A call with one argument may drop its brackets. It binds tighter than any operator.

len xs - 1           # len(xs) - 1
print len xs         # print(len(xs))
set f y for y in xs  # set(f(y) for y in xs)

Ranges¶

lo..hi   # range(lo, hi + 1)
lo..<hi  # range(lo, hi)

Lambdas¶

A lambda may appear only as a call argument or as the value of an assignment.

x -> x * 2       # lambda x: x * 2
(a, b) -> a + b  # takes a and b, or one pair that it unpacks
() -> []         # takes nothing

_ may be used more than once among the names: (_, r) -> r.

gain = (p, t) -> (p + 1) / (t + 1) - p / t

Folds¶

sum, max, min and count followed by for form a fold.

sum for x in xs: x * x
max from 0 for x in xs if x > 0: x
count for x in xs if x % 2 == 0

from e gives the starting value. For max and min it is also the value of a fold over nothing.
if cond skips items.
count counts the items for which the condition, and the value after : if there is one, are true.

A fold may take a block instead of : value. The block runs once per item, and its last line is the value folded in.

sum for p in scan(+, nums)
  got = cnt[p - k]
  cnt[p] += 1
  got

First true¶

first k in lo..hi if pred

The least k in the range for which pred is true. pred must be monotone: false, then true. It compiles to bisect_left with a key, so it runs in O(log n) evaluations of pred. If pred is never true the value is one past the end of the range.

Memoized functions¶

memo f(i, j) =
  | i == len(a) or j == len(b) -> 0
  | a[i] == b[j]               -> 1 + f(i + 1, j + 1)
  | else                       -> max(f(i + 1, j), f(i, j + 1))

Each case is | guard -> value, tried in order; | else -> matches everything. A one-line form memo f(x) = expr has no cases. The function is cached with functools.cache. A method that defines a memo runs on a thread with a 256 MB stack and a raised recursion limit, so recursion depth of 10^4 and beyond is safe.

Calls with special meaning¶

ceil(a / b)     # -(-(a) // (b)), exact integers
floor(a / b)    # (a) // (b)
sort(xs, by=f)  # sorted(xs, key=f)
scan(+, xs)     # accumulate(xs)
scan(*, xs)     # accumulate(xs, operator.mul)
scan(f, xs)     # accumulate(xs, f)
counter(xs)     # Counter(xs)

Helpers¶

A call to any of these names includes the helper's source in the output, so the Python runs on LeetCode unchanged.

cells(grid)                           # every (i, j), row by row
cells(grid, start=1)                  # only i, j >= 1
cells(grid, eq=0)                     # only cells holding 0
cells(grid, gte=k)                    # only cells holding k or more; also lt, lte, gt
nbrs(grid, i, j)                      # on-grid neighbours: up, left, right, down
nbrs(grid, p)                         # the same, with the cell as one pair
nbrs(grid, p, eq=inf)                 # only neighbours holding inf; same comparisons
table(m, n, fill=0)                   # m rows of n cells
like(grid, fill=inf)                  # a new table with the shape of grid
shape(grid)                           # (rows, cols); shape(a, b) is (len(a), len(b))
shape(grid, last_index=True)          # the index of the last cell
put(grid, at, v)                      # grid[i][j] = v for every (i, j) in at
pairs(n)                              # every (i, j) with 0 <= i < j < n
levels(q)                             # pops deque q level by level, yields (d, item)
levels(q, grouped=True)               # yields (d, items), one level at a time
levels(q, grid, seen, gte=k)          # drops items seen before or whose value fails
adjacency(edges)                      # adjacency lists; also n, reverse, directed, weighted
indegrees(edges)                      # in-degree of every vertex; same flags
components(land, p -> nbrs(grid, p))  # connected components
graph(vs, edges)                      # a weighted graph; an edge (u, v) has weight 1
dijkstra(g, src)                      # shortest distance to every vertex, inf if unreachable
in_bounds(grid, i, j)                 # True if (i, j) is a cell of grid
in_bounds(grid, p)                    # the same, with the cell as one pair
edges(grid)                           # every (i, j) on the border, row by row
is_edge(grid, i, j)                   # True if (i, j) is on the first or last row or column
grid_bfs(grid, sources)               # steps from the nearest source to every cell, -1 if none
grid_bfs(grid, sources, ok=v -> v == 0)  # enters a cell only if ok(grid[cell]); also dirs
triples(n)                            # every (i, j, k) with 0 <= i < j < k < n
ceil_div(a, b)                        # (a + b - 1) // b
first_true(lo, hi, ok)                # smallest x in lo..hi with ok(x); hi + 1 if none
last_true(lo, hi, ok)                 # largest x in lo..hi with ok(x); lo - 1 if none
first_false(lo, hi, ok)               # smallest x in lo..hi without ok(x); hi + 1 if none
last_false(lo, hi, ok)                # largest x in lo..hi without ok(x); lo - 1 if none
min_chunks(nums, cap)                 # fewest runs of nums each summing to at most cap; inf if one exceeds cap
Multiset()                            # a Counter that drops a key when its count reaches 0
heap(xs)                              # a min-heap of xs
heap(xs, type=max)                    # a max-heap of xs

Items pushed onto q while levels(q) runs are yielded at the next level.

A heap has push(x), pop(), peek() and len. Iterating over a heap gives its items in no particular order.

cells, nbrs, table, like, shape, put, pairs, levels, adjacency, indegrees, in_bounds, is_edge, edges, grid_bfs, triples, ceil_div, first_true, last_true, first_false, last_false, min_chunks, Multiset match the harness builtins of the same names in utils/harness/. mu/test_mu.py checks that the two agree.