English
bitIndices is defined as the binary-recursor applied to the natural numbers to produce a list of indices with 1-bits.
Русский
bitIndices задаётся как бинарная рекуррундер по натуральному числу, формирующая список индексов единиц двоичного разложения.
LaTeX
$$bitIndices(n) = @binaryRec (fun _ => List Nat) [] (fun b _ s => b.casesOn (s.map (·+1)) (0 :: s.map (·+1))) n$$
Lean4
/-- The function which maps each natural number `∑ i ∈ s, 2^i` to the list of
elements of `s` in increasing order. -/
def bitIndices (n : ℕ) : List ℕ :=
@binaryRec (fun _ ↦ List ℕ) [] (fun b _ s ↦ b.casesOn (s.map (· + 1)) (0 :: s.map (· + 1))) n
