1# list - operations on lists.2#3# Everything returns a new list, nothing is modified in place except Sort,4# which sorts a copy.56cmp = import("cmp")78# Each calls f(x) for every element.9Each = fn(xs, f) {10 for i = 0; i < len(xs); ++i {11 f(xs[i])12 }13}1415# Map returns the list of f(x) for every element.16Map = fn(xs, f) {17 out = []18 for i = 0; i < len(xs); ++i {19 out = append(out, f(xs[i]))20 }21 return out22}2324# Filter returns the elements for which f(x) is true.25Filter = fn(xs, f) {26 out = []27 for i = 0; i < len(xs); ++i {28 if f(xs[i]) {29 out = append(out, xs[i])30 }31 }32 return out33}3435# Reduce folds the list from the left starting from acc.36Reduce = fn(xs, acc, f) {37 for i = 0; i < len(xs); ++i {38 acc = f(acc, xs[i])39 }40 return acc41}4243# Index returns the position of the first element equal to x, -1 if absent.44Index = fn(xs, x) {45 for i = 0; i < len(xs); ++i {46 if cmp.Equal(xs[i], x) {47 return i48 }49 }50 return -151}5253# Contains reports whether x is in xs.54Contains = fn(xs, x) { Index(xs, x) >= 0 }5556# Find returns the first element for which f(x) is true, null if there is none.57Find = fn(xs, f) {58 for i = 0; i < len(xs); ++i {59 if f(xs[i]) {60 return xs[i]61 }62 }63 return null64}6566# Copy returns a new list with the same elements. slice() would share the67# same underlying array, so writing into it would touch the original.68Copy = fn(xs) {69 out = []70 for i = 0; i < len(xs); ++i {71 out = append(out, xs[i])72 }73 return out74}7576# Reverse returns the elements in the opposite order.77Reverse = fn(xs) {78 out = []79 for i = len(xs) - 1; i >= 0; --i {80 out = append(out, xs[i])81 }82 return out83}8485# Range returns the integers from start (included) to stop (excluded).86Range = fn(start, stop) {87 out = []88 for i = start; i < stop; ++i {89 out = append(out, i)90 }91 return out92}9394# Join concatenates the elements as strings separated by sep.95Join = fn(xs, sep) {96 out = ""97 for i = 0; i < len(xs); ++i {98 if i > 0 {99 out = out + sep100 }101 out = out + string(xs[i])102 }103 return out104}105106# Sort returns the elements ordered by less(a, b), which must be true when a107# comes first. Pass null to order with the < operator.108Sort = fn(xs, less) {109 if less == null {110 less = fn(a, b) { a < b }111 }112 return quicksort(Copy(xs), 0, len(xs) - 1, less)113}114115quicksort = fn(xs, lo, hi, less) {116 if lo >= hi {117 return xs118 }119120 # Median of the ends and the middle, so that an already sorted list121 # doesn't degenerate into O(n^2).122 mid = lo + (hi - lo) / 2123 if less(xs[mid], xs[lo]) { xs = swap(xs, mid, lo) }124 if less(xs[hi], xs[lo]) { xs = swap(xs, hi, lo) }125 if less(xs[hi], xs[mid]) { xs = swap(xs, hi, mid) }126 xs = swap(xs, mid, hi)127128 pivot = xs[hi]129 i = lo130 for j = lo; j < hi; ++j {131 if less(xs[j], pivot) {132 xs = swap(xs, i, j)133 ++i134 }135 }136 xs = swap(xs, i, hi)137138 xs = quicksort(xs, lo, i - 1, less)139 return quicksort(xs, i + 1, hi, less)140}141142swap = fn(xs, i, j) {143 tmp = xs[i]144 xs[i] = xs[j]145 xs[j] = tmp146 return xs147}