spec/lib/u32seq.bend

bend-collections-laws-containers@1.0.0.0 · 28 lines · 0 definitions

1import Base
2import bend-collections-laws-containers@1.0.0.0/spec/lib/common.bend as C
3
4# Sequences of U32 values with wrapping (mod 2^32) addition, shared by the
5# Fenwick and segment tree specifications. Imports only spec/ and Base.
6
7# Sum of all elements, wrapping modulo 2^32 (U32.add).
8def sum(xs: List<&2, U32>) -> U32:
9  match xs:
10    case Nil{}:
11      0
12    case Con{h, t}:
13      U32.add(h, sum(t))
14
15# The elements with index in [l, r).
16def slice(xs: List<&2, U32>, +l: Nat, r: Nat) -> List<&2, U32>:
17  C.take(U32, C.drop(U32, xs, l), Nat.sub(r, l))
18
19def zeros(n: Nat) -> List<&2, U32>:
20  C.replicate(U32, n, 0)
21
22# Every element increased by v (wrapping).
23def add_each(xs: List<&2, U32>, +v: U32) -> List<&2, U32>:
24  match xs:
25    case Nil{}:
26      Nil{}
27    case Con{h, t}:
28      Con{U32.add(h, v), add_each(t, v)}