module fp
module lib/fp.mu
import "fp"fp provides high-level functions for functional programming.
Every function here is non-mutating: it reads its input and returns a fresh list. Nothing in this module writes through its argument, so a caller can always keep using the list it passed in. iter is the lazy counterpart with the same vocabulary.
Functions
any#
any returns true as soon as predicate holds for an element.
Source lib/fp.mu:153
fn any(arr, predicate) {
i := 0
while i < len(arr) {
if predicate(arr[i]) {
return true
}
i = i + 1
}
return false
}chunk#
chunk splits arr into subarrays each at most size long.
Source lib/fp.mu:344
fn chunk(arr, size) {
if size <= 0 {
return []
}
result := []
i := 0
while i < len(arr) {
end := i + size
if end > len(arr) {
end = len(arr)
}
chunk := []
j := i
while j < end {
chunk = append(chunk, arr[j])
j = j + 1
}
result = append(result, chunk)
i = end
}
return result
}combinations#
combinations returns every size-element combination from arr.
Input order is preserved, so each combination is produced once and permutations of the same selected positions are not included.
Example:
combinations([1, 2, 3, 4], 2)returns:
[
[1, 2], [1, 3], [1, 4],
[2, 3], [2, 4],
[3, 4]
]Source lib/fp.mu:568
fn combinations(arr, size) {
if size < 0 || size > len(arr) {
return []
}
if size == 0 {
return [[]]
}
return flat_map(range(0, len(arr) - size + 1), fn(i) {
tails := combinations(drop(arr, i + 1), size - 1)
return map(tails, fn(tail) {
return _prepend(arr[i], tail)
})
})
}compose#
compose builds a unary function that applies g before f.
Source lib/fp.mu:14
fn compose(f, g) {
return fn(input) {
return f(g(input))
}
}contains#
contains reports whether the list holds an element equal to value.
Source lib/fp.mu:405
fn contains(arr, value) {
return index_of(arr, value) >= 0
}count#
count tallies the number of elements satisfying predicate.
Source lib/fp.mu:241
fn count(arr, predicate) {
tally := 0
i := 0
while i < len(arr) {
if predicate(arr[i]) {
tally = tally + 1
}
i = i + 1
}
return tally
}drop#
drop skips the first limit elements and returns the remainder.
Source lib/fp.mu:304
fn drop(arr, limit) {
// Dropping nothing still copies -- see the note in rotate.
if limit <= 0 {
return _copy(arr)
}
if limit >= len(arr) {
return []
}
result := []
i := limit
while i < len(arr) {
result = append(result, arr[i])
i = i + 1
}
return result
}every#
every returns true only if predicate holds for every element.
Source lib/fp.mu:141
fn every(arr, predicate) {
i := 0
while i < len(arr) {
if !predicate(arr[i]) {
return false
}
i = i + 1
}
return true
}filter#
filter returns all elements that satisfy predicate.
Source lib/fp.mu:67
fn filter(arr, predicate) {
result := []
i := 0
while i < len(arr) {
item := arr[i]
if predicate(item) {
result = append(result, item)
}
i = i + 1
}
return result
}find#
find returns the first element satisfying predicate or nil.
Source lib/fp.mu:385
fn find(arr, predicate) {
i := 0
while i < len(arr) {
item := arr[i]
if predicate(item) {
return item
}
i = i + 1
}
return nil
}find_index#
find_index returns the index of the first matching element or -1.
Source lib/fp.mu:470
fn find_index(arr, predicate) {
i := 0
while i < len(arr) {
if predicate(arr[i]) {
return i
}
i = i + 1
}
return -1
}flat_map#
flat_map maps each element and flattens any intermediate collections.
Source lib/fp.mu:46
fn flat_map(arr, transform) {
result := []
i := 0
while i < len(arr) {
mapped := transform(arr[i])
j := 0
while j < len(mapped) {
result = append(result, mapped[j])
j = j + 1
}
i = i + 1
}
return result
}flatten#
flatten collapses one level of nesting by delegating to flat_map with identity.
Source lib/fp.mu:62
fn flatten(arr) {
return flat_map(arr, identity)
}fold_right#
fold_right processes elements from right to left with combiner.
Source lib/fp.mu:131
fn fold_right(arr, acc, combiner) {
i := len(arr) - 1
while i >= 0 {
acc = combiner(arr[i], acc)
i = i - 1
}
return acc
}group_by#
group_by buckets elements by keys produced by classifier.
Source lib/fp.mu:498
fn group_by(arr, classifier) {
groups := {}
i := 0
while i < len(arr) {
item := arr[i]
key := classifier(item)
bucket := groups[key]
if bucket == nil {
bucket = []
}
bucket = append(bucket, item)
groups[key] = bucket
i = i + 1
}
return groups
}identity#
identity returns the provided value unchanged.
Source lib/fp.mu:9
fn identity(value) {
return value
}index_of#
index_of returns the position of the first element equal to value, or -1.
Source lib/fp.mu:398
fn index_of(arr, value) {
return find_index(arr, fn(item) {
return item == value
})
}interleave#
interleave weaves elements from arr1 and arr2 alternately.
Source lib/fp.mu:221
fn interleave(arr1, arr2) {
result := []
i := 0
N := len(arr1)
if len(arr2) > N {
N = len(arr2)
}
while i < N {
if i < len(arr1) {
result = append(result, arr1[i])
}
if i < len(arr2) {
result = append(result, arr2[i])
}
i = i + 1
}
return result
}map#
map applies transform to every element and returns the collected results.
Source lib/fp.mu:28
fn map(arr, transform) {
result := []
i := 0
while i < len(arr) {
result = append(result, transform(arr[i]))
i = i + 1
}
return result
}max#
max returns the largest element of a non-empty list.
Source lib/fp.mu:81
fn max(arr) {
if len(arr) == 0 {
return error("fp.max of empty list")
}
return reduce(arr, arr[0], fn(a, b) {
if a > b {
return a
}
return b
})
}min#
min returns the smallest element of a non-empty list.
Source lib/fp.mu:95
fn min(arr) {
if len(arr) == 0 {
return error("fp.min of empty list")
}
return reduce(arr, arr[0], fn(a, b) {
if a < b {
return a
}
return b
})
}partition#
partition divides arr into truthy and falsy buckets per predicate.
Source lib/fp.mu:368
fn partition(arr, predicate) {
truthy := []
falsy := []
i := 0
while i < len(arr) {
item := arr[i]
if predicate(item) {
truthy = append(truthy, item)
} else {
falsy = append(falsy, item)
}
i = i + 1
}
return [truthy, falsy]
}permutations#
permutations returns every ordered selection of size elements from arr. If size is omitted, all full-length permutations are returned.
Elements are selected by position. If arr contains duplicate values, duplicate-looking permutations may therefore be present in the result.
Example:
permutations([1, 2, 3], 2)returns:
[
[1, 2], [1, 3],
[2, 1], [2, 3],
[3, 1], [3, 2]
]Source lib/fp.mu:601
fn permutations(arr, size...) {
n := len(arr)
r := n
if len(size) > 0 {
r = size[0]
}
if r < 0 || r > n {
return []
}
if r == 0 {
return [[]]
}
return flat_map(range(0, n), fn(i) {
rest := _without_index(arr, i)
tails := permutations(rest, r - 1)
return map(tails, fn(tail) {
return _prepend(arr[i], tail)
})
})
}pipe#
pipe calls f first and then routes its result into g.
Source lib/fp.mu:21
fn pipe(f, g) {
return fn(input) {
return g(f(input))
}
}range#
range produces a sequence from start (inclusive) to stop (exclusive) stepping by step.
Source lib/fp.mu:165
fn range(start, stop, step...) {
stepVal := 1
if len(step) > 0 {
stepVal = step[0]
}
if stepVal == 0 {
return []
}
result := []
current := start
if stepVal > 0 {
while current < stop {
result = append(result, current)
current = current + stepVal
}
} else {
while current > stop {
result = append(result, current)
current = current + stepVal
}
}
return result
}reduce#
reduce accumulates from the left using combiner and the evolving acc.
Source lib/fp.mu:109
fn reduce(arr, acc, combiner) {
i := 0
while i < len(arr) {
acc = combiner(acc, arr[i])
i = i + 1
}
return acc
}reverse#
reverse returns a new list with the elements in the opposite order.
Source lib/fp.mu:410
fn reverse(arr) {
result := []
i := len(arr) - 1
while i >= 0 {
result = append(result, arr[i])
i = i - 1
}
return result
}rotate#
rotate shifts the list circularly by offset positions.
Source lib/fp.mu:254
fn rotate(arr, offset) {
length := len(arr)
if length == 0 {
return []
}
shift := offset % length
if shift < 0 {
shift = shift + length
}
// A zero shift still copies. Handing the input straight back would make the
// result an ALIAS -- appending to it would then grow the caller's list -- and
// a function whose return value is sometimes shared and sometimes not is a
// trap wherever it is used.
if shift == 0 {
return _copy(arr)
}
result := []
start := length - shift
i := start
while i < length {
result = append(result, arr[i])
i = i + 1
}
i = 0
while i < start {
result = append(result, arr[i])
i = i + 1
}
return result
}scan#
scan produces all intermediate accumulator values while folding left.
Source lib/fp.mu:119
fn scan(arr, acc, combiner) {
result := []
i := 0
while i < len(arr) {
acc = combiner(acc, arr[i])
result = append(result, acc)
i = i + 1
}
return result
}slice#
slice returns the elements from start (inclusive) to end (exclusive) as a new list. Both bounds are clamped to the list, so a slice can never fail -- an inverted or out-of-range range simply yields fewer elements.
Source lib/fp.mu:325
fn slice(arr, start, end) {
from := start
if from < 0 {
from = 0
}
to := end
if to > len(arr) {
to = len(arr)
}
result := []
i := from
while i < to {
result = append(result, arr[i])
i = i + 1
}
return result
}sliding#
sliding returns all overlapping windows of size elements.
Example:
sliding([1, 2, 3, 4, 5], 3)returns:
[
[1, 2, 3],
[2, 3, 4],
[3, 4, 5]
]Source lib/fp.mu:528
fn sliding(arr, size) {
if size <= 0 || size > len(arr) {
return []
}
result := []
i := 0
while i + size <= len(arr) {
window := []
j := 0
while j < size {
window = append(window, arr[i + j])
j = j + 1
}
result = append(result, window)
i = i + 1
}
return result
}sort#
sort returns a new list with the elements in ascending order. Elements are compared with <, so they must be mutually comparable -- all integers, or all strings.
Source lib/fp.mu:423
fn sort(arr) {
return sort_by(arr, identity)
}sort_by#
sort_by returns a new list ordered by the value that key returns for each element, so sort_by(people, fn(p) { return p["age"] }) orders by age.
The sort is stable: elements whose keys compare equal keep the order they arrived in, which is what makes sorting by one field and then another do what it looks like it does.
Source lib/fp.mu:433
fn sort_by(arr, key) {
if len(arr) <= 1 {
return _copy(arr)
}
mid := len(arr) / 2
left := sort_by(take(arr, mid), key)
right := sort_by(drop(arr, mid), key)
return _merge(left, right, key)
}sum#
sum returns the sum of a list of numbers.
Source lib/fp.mu:39
fn sum(xs) {
return reduce(xs, 0, fn(a, b) {
return a + b
})
}take#
take returns the first limit elements, bounded by the array length.
Source lib/fp.mu:286
fn take(arr, limit) {
if limit <= 0 {
return []
}
if limit > len(arr) {
limit = len(arr)
}
result := []
i := 0
while i < limit {
result = append(result, arr[i])
i = i + 1
}
return result
}uniq#
uniq removes duplicates while preserving the first occurrence order.
Source lib/fp.mu:482
fn uniq(arr) {
result := []
i := 0
while i < len(arr) {
item := arr[i]
// The result IS the record of what has been seen; a second list tracking
// the same thing can only ever agree with it.
if !contains(result, item) {
result = append(result, item)
}
i = i + 1
}
return result
}zip#
zip pairs elements from arr1 and arr2 until one runs out.
Source lib/fp.mu:191
fn zip(arr1, arr2) {
result := []
i := 0
N := len(arr1)
if len(arr2) < N {
N = len(arr2)
}
while i < N {
result = append(result, [arr1[i], arr2[i]])
i = i + 1
}
return result
}zip_with#
zip_with combines corresponding elements of arr1 and arr2 via combiner.
Source lib/fp.mu:206
fn zip_with(arr1, arr2, combiner) {
result := []
i := 0
N := len(arr1)
if len(arr2) < N {
N = len(arr2)
}
while i < N {
result = append(result, combiner(arr1[i], arr2[i]))
i = i + 1
}
return result
}Internal helpers
Underscore-prefixed names are implementation detail. They are listed so the module's source reads without surprises, not as API — they may change at any time.
| _copy(arr) | _copy returns a fresh list holding the same elements. |
| _merge(left, right, key) | _merge interleaves two already-sorted lists. |
| _prepend(value, arr) | _prepend returns a fresh list with value followed by arr. |
| _without_index(arr, index) | _without_index returns a fresh list containing every element except arr[index]. |