1	import Base
2	import ./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).
8	def 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).
16	def 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	
19	def zeros(n: Nat) -> List<&2, U32>:
20	  C.replicate(U32, n, 0)
21	
22	# Every element increased by v (wrapping).
23	def 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)}