list.nula

// Nulang standard library — list/array operations over native arrays.
// Language version: 2.0.0-alpha
//
// Polymorphic functions (map, filter, reverse, take, drop, range, length,
// contains, any, all) work with any element type. Functions with explicit
// [Int] annotations (sum, index_of, find, fold, max_of, min_of, sort, append,
// zip, enumerate, uniq) are Int-only for now.
//
// Built on `perform Array.push` / `perform Array.new` / `perform Array.length`
// primitives (added 2026-07-30).
/// Number of elements in the array.
pub fn length(xs) -> Int {
    var n = 0;
    for _x in xs {
        n = n + 1
    };
    n
}

/// Sum of all elements.
pub fn sum(xs: [Int]) -> Int {
    var total = 0;
    for x in xs {
        total = total + x
    };
    total
}

/// True if x appears in xs.
pub fn contains(x, xs) -> Bool {
    for elem in xs {
        if elem == x then { return true } else {}
    };
    false
}

/// First index of x in xs, or -1 if not found.
pub fn index_of(x, xs) -> Int {
    var i = 0;
    for elem in xs {
        if elem == x then { return i } else {};
        i = i + 1
    };
    -1
}

/// True if any element satisfies the predicate.
pub fn any(pred, xs) -> Bool {
    for x in xs {
        if pred(x) then { return true } else {}
    };
    false
}

/// True if all elements satisfy the predicate.
pub fn all(pred, xs) -> Bool {
    for x in xs {
        if !pred(x) then { return false } else {}
    };
    true
}

/// First element satisfying pred, or -1 if none match.
pub fn find(pred, xs) {
    for x in xs {
        if pred(x) then { return x } else {}
    };
    -1
}

/// Left fold: fold(f, init, [a, b, c]) = f(f(f(init, a), b), c).
pub fn fold(f, init: Int, xs: [Int]) -> Int {
    var acc = init;
    for x in xs {
        acc = f(acc, x)
    };
    acc
}

/// Maximum element. Crashes (negative return) for empty array.
pub fn max_of(xs: [Int]) -> Int {
    var first = true;
    var best = 0;
    for x in xs {
        if first then { best = x; first = false } else {
            if x > best then { best = x } else {}
        }
    };
    best
}

/// Minimum element. Crashes (negative return) for empty array.
pub fn min_of(xs: [Int]) -> Int {
    var first = true;
    var best = 0;
    for x in xs {
        if first then { best = x; first = false } else {
            if x < best then { best = x } else {}
        }
    };
    best
}

// ---------------------------------------------------------------------------
// Array-producing functions (require `perform Array.*` builtins)
// ---------------------------------------------------------------------------

/// Map: apply f to each element, return new array.
pub fn map(f, xs) {
    var result = [];
    for x in xs {
        result = perform Array.push(result, f(x))
    };
    result
}

/// Filter: keep elements where pred returns true.
pub fn filter(pred, xs) {
    var result = [];
    for x in xs {
        if pred(x) then { result = perform Array.push(result, x) } else {}
    };
    result
}

/// Reverse: return new array with elements in reverse order.
pub fn reverse(xs) {
    var result = [];
    var i = perform Array.length(xs) - 1;
    while i >= 0 {
        result = perform Array.push(result, xs[i]);
        i = i - 1
    };
    result
}

/// Take first n elements.
pub fn take(n, xs) {
    var result = [];
    var i = 0;
    var len = perform Array.length(xs);
    while i < n && i < len {
        result = perform Array.push(result, xs[i]);
        i = i + 1
    };
    result
}

/// Drop first n elements.
pub fn drop(n, xs) {
    var result = [];
    var i = n;
    var len = perform Array.length(xs);
    while i < len {
        result = perform Array.push(result, xs[i]);
        i = i + 1
    };
    result
}

/// Range: array of [0, 1, ..., n-1].
pub fn range(n) {
    var result = [];
    var i = 0;
    while i < n {
        result = perform Array.push(result, i);
        i = i + 1
    };
    result
}

/// Quicksort: returns a new sorted array (ascending).  Original unchanged.
/// Picks the first element as pivot; partitions via `filter` into less,
/// equal, and greater slices, then recurses.  Handles empty, single-element,
/// duplicates, and negative numbers correctly.
pub fn sort(xs: [Int]) -> [Int] {
    var len = perform Array.length(xs);
    if len <= 1 then { xs } else {
        var pivot = xs[0];
        var less = filter(fn(x) { x < pivot }, xs);
        var eq = filter(fn(x) { x == pivot }, xs);
        var greater = filter(fn(x) { x > pivot }, xs);
        var result = sort(less);
        for x in eq {
            result = perform Array.push(result, x)
        };
        for x in sort(greater) {
            result = perform Array.push(result, x)
        };
        result
    }
}

/// Sort using comparator cmp(a, b) that returns true if a should come before b.
/// Same quicksort as `sort`, but uses cmp for the partition instead of < and >.
pub fn sort_by(cmp, xs) {
    var len = perform Array.length(xs);
    if len <= 1 then { xs } else {
        var pivot = xs[0];
        var less = filter(fn(x) { cmp(x, pivot) }, xs);
        var eq = filter(fn(x) { !cmp(x, pivot) && !cmp(pivot, x) }, xs);
        var greater = filter(fn(x) { cmp(pivot, x) }, xs);
        var result = sort_by(cmp, less);
        for x in eq {
            result = perform Array.push(result, x)
        };
        for x in sort_by(cmp, greater) {
            result = perform Array.push(result, x)
        };
        result
    }
}

/// Minimum element according to comparator cmp(a, b) returning true if a is "less than" b.
/// Returns 0 for empty array (matching max_of/min_of convention).
pub fn min_by(cmp, xs) {
    var first = true;
    var best = 0;
    for x in xs {
        if first then { best = x; first = false } else {
            if cmp(x, best) then { best = x } else {}
        }
    };
    best
}

/// Maximum element according to comparator cmp(a, b) returning true if a is "less than" b.
/// Returns 0 for empty array (matching max_of/min_of convention).
pub fn max_by(cmp, xs) {
    var first = true;
    var best = 0;
    for x in xs {
        if first then { best = x; first = false } else {
            if cmp(best, x) then { best = x } else {}
        }
    };
    best
}

/// Concatenate two arrays into a new array.  Original arrays unchanged.
pub fn append(xs: [Int], ys: [Int]) -> [Int] {
    var result = xs;
    for x in ys {
        result = perform Array.push(result, x)
    };
    result
}

/// Zip two arrays into an array of tuples. Result length = min(len(xs), len(ys)).
pub fn zip(xs: [Int], ys: [Int]) {
    var result = [];
    var i = 0;
    var len_x = perform Array.length(xs);
    var len_y = perform Array.length(ys);
    while i < len_x && i < len_y {
        result = perform Array.push(result, (xs[i], ys[i]));
        i = i + 1
    };
    result
}

/// Enumerate: returns [(0, xs[0]), (1, xs[1]), ...].
pub fn enumerate(xs: [Int]) {
    var result = [];
    var i = 0;
    var len = perform Array.length(xs);
    while i < len {
        result = perform Array.push(result, (i, xs[i]));
        i = i + 1
    };
    result
}

/// Remove duplicates, preserving first-occurrence order.
pub fn uniq(xs: [Int]) -> [Int] {
    var result = [];
    for x in xs {
        if !contains(x, result) then { result = perform Array.push(result, x) } else {}
    };
    result
}