listutils.fn

namespace

// member: #a -> list(#a) -> bool
fn member {
    (_, []) { false }
    (x, x @ _) { true }
    (x, _ @ t) { member(x, t) }
}

// unique: list(#a) -> list(#a)
fn unique {
    ([]) { [] }
    (h @ t) {
        if (member(h, t)) {
            unique(t)
        } else {
            h @ unique(t)
        }
    }
}

// exclude: list(#t) -> list(#t) -> list(#t)
fn exclude {
    (items, []) { [] }
    (items, h @ t) {
        if (member(h, items)) {
            exclude(items, t)
        } else {
            h @ exclude(items, t)
        }
    }
}

// map: (#a -> #b) -> list(#a) -> list(#b)
fn map {
    (_, []) { [] }
    (func, h @ t) { func(h) @ map(func, t) }
}

// map_prefix: (#a -> #b) -> list(#a) -> list(#b) -> list(#b)
fn map_prefix(func, lst, tail) {
    let
        fn helper {
            ([]) { tail }
            (h @ t) { func(h) @ helper(t) }
        }
    in
        helper(lst)
}

// length: list(#s) -> number
fn length(lst) {
    let
        fn helper {
            ([], n) { n }
            (_ @ t, n) { helper(t, n + 1) }
        }
    in
        helper(lst, 0)
}

// foldl (#a -> #b -> #b) -> #b -> list(#a) -> #b
fn foldl {
    (_, acc, []) { acc }
    (func, acc, h @ t) { foldl(func, func(h, acc), t) }
}

// foldr (#a -> #b -> #b) -> #b -> list(#a) -> #b
fn foldr(func, acc, lst) {
    foldl(func, acc, reverse(lst))
}

// foldl1 (#a -> #a -> #a) -> list(#a) -> #a
fn foldl1 {
    (func, h @ t) {
        foldl(func, h, t)
    }
    (_, _) { error("foldl1") }
}

// foldr1 (#a -> #a -> #a) -> list(#a) -> #a
fn foldr1(func, lst) {
    foldl1(func, reverse(lst))
}

// reverse: list)#a) -> list(#a)
fn reverse (lst) {
    foldl(fn (elem, acc) { elem @ acc }, [], lst)
}

// scanl: (#a -> #b -> #b) -> #a-> list(#a) -> list(list(#b))
fn scanl (func, acc, lst) {
    let unsafe fn scan {
        (acc, []) { acc }
        (acc = acc_h @ _, lst_h @ lst_t) { scan(func(lst_h, acc_h) @ acc, lst_t) }
    }
    in scan([acc], lst)
}

// filter: (#a -> bool) -> list(#a) -> list(#a)
fn filter {
    (f, []) { [] }
    (f, h @ t) {
        if (f(h)) {
            h @ filter(f, t)
        } else {
            filter(f, t)
        }
    }
}

// filter_out: (#a -> bool) -> list(#a) -> list(#a)
fn filter_not (f, l) {
    filter(fn (x) { not f(x) }, l)
}

// indices: (#a -> bool) -> list(#a) -> list(number)
// like filter but returns the indices of the matching elements
fn indices(f, lst) {
    let
        fn helper {
            ([], _) { [] }
            (h @ t, n) {
                if (f(h)) {
                    n @ helper(t, n + 1)
                } else {
                    helper(t, n + 1)
                }
            }
        }
    in
        helper(lst, 0)
}

// nths: list(number) -> list(#a) -> list(#a)
fn nths (indices, lst) {
    map(fn (n) { nth(n, lst) }, indices)
}

// except_nth: number -> list(#a) -> list(#a)
fn except_nth (index, lst) {
    let
        fn helper {
            ([], _) { [] }
            (h @ t, n) {
                if (n == index) {
                    helper(t, n + 1)
                } else {
                    h @ helper(t, n + 1)
                }
            }
        }
    in
        helper(lst, 0)
}

// concat: list(list(#a)) -> list(#a)
fn concat(lst) {
    foldr(fn (elem, acc) { elem @@ acc }, [], lst)
}

// join: list(#a) -> list(list(#a)) -> list(#a)
fn join(sep, lst) {
    foldr(fn {
        (elem, []) { elem }
        (elem, acc) { elem @@ sep @@ acc }
    }, [], lst)
}

// any: (#a -> bool) -> list(#a) -> bool
fn any {
    (_, []) { false }
    (f, h @ t) { f(h) or any(f, t) }
}

// none: (#a -> bool) -> list(#a) -> bool
fn none(f, l) {
    not any(f, l)
}

// all: (#a -> bool) -> list(#a) -> bool
fn all {
    (_, []) { true }
    (f, h @ t) { f(h) and all(f, t) }
}

// repeat: number -> #a -> list(#a)
fn repeat {
    (0, _) { [] }
    (n, v) { v @ repeat(n - 1, v) }
}

// repeat_prefix: number -> #a -> list(#a) -> list(#a)
// repeat_prefix(n, item, list) is a more efficient way of doing repeat(n, item) @@ list
fn repeat_prefix(n, v, tail) {
    let
        fn helper {
            (0) { tail }
            (n) { v @ helper(n - 1) }
        }
    in
        helper(n)
}

// nth: number -> list(#a) -> #a
fn nth {
    (0, h @ _) { h }
    (n, _ @ t) { nth(n - 1, t) }
    (_, _) { error("nth") }
}

// sum: list(number) -> number
fn sum(lst) {
    foldl(fn (elm, acc) { elm + acc }, 0, lst)
}

// product: list(number) -> number
fn product(lst) {
    foldl(fn (elm, acc) { elm * acc }, 1, lst)
}

// zip: list(#a) -> list(#b) -> list(#(#a, #b))
fn zip(a, b) {
    zipWith(fn (x, y) { #(x, y) }, a, b)
}

// zipwith: (#a -> #b -> #c) -> list(#a) -> list(#b) -> list(#c)
fn zipWith {
    (f, h1 @ t1, h2 @ t2) { f(h1, h2) @ zipWith(f, t1, t2) }
    (_, _, _) { [] }
}

// unzip: list(#(#a, #b)) -> #(list(#a), list(#b))
fn unzip {
    ([]) { #([], []) }
    (#(x, y) @ rest) {
        switch (unzip(rest)) {
            (#(xs, ys)) { #(x @ xs, y @ ys) }
        }
    }
}

// last: list(#a) -> #a
fn last {
    ([]) { error("last") }
    ([a]) { a }
    (_ @ t) { last(t) }
}

// empty: list(#a) -> bool
fn empty {
    ([]) { true }
    (_) { false }
}

// take: number -> list(#a) -> list(#a)
fn take {
    (0, _) { [] }
    (n, []) { [] }
    (n, h @ t) { h @ take(n - 1, t) }
}

// drop: number -> list(#a) -> list(#a)
fn drop {
    (0, l) { l }
    (n, []) { [] }
    (n, _ @ t) { drop(n - 1, t) }
}

// minimum: list(#a) -> #a
fn minimum(lst) {
    foldl1(fn (elem, acc) { if (elem < acc) { elem } else { acc } }, lst)
}

// maximum: list(#a) -> #a
fn maximum(lst) {
    foldl1(fn (elem, acc) { if (elem > acc) { elem } else { acc } }, lst)
}

// range: number -> number -> list(number)
fn range(low, high) {
    let
        fn helper(h, acc) {
            if (h < low) {
                acc
            } else {
                helper(h - 1, h @ acc)
            }
        }
    in
        helper(high, [])
}

// dedup: list(#a) -> list(#a)
// TCO, but does not preserve order
fn dedup(lst) {
    let
        fn helper {
            ([], acc) { acc }
            (h @ t, acc) {
                helper(filter(fn (i) { h != i }, t), h @ acc)
            }
        }
    in
        helper(lst, [])
}

// sortBy: (#a -> #a -> cmp) -> list(#a) -> list(#a)
fn sortBy(predicate, lst) {
    let
        fn full_sort {
            ([]) { [] }
            (first @ rest) {
                partition(first, rest, fn (lesser, greater) {
                    partial_sort(lesser, first @ full_sort(greater))
                })
            }
        }
        fn partial_sort {
            (first @ rest, already_sorted) {
                partition(first, rest, fn (lesser, greater) {
                    partial_sort(lesser, first @ partial_sort(greater, already_sorted))
                })
            }
            ([], already_sorted) { already_sorted }
        }
        fn partition(key, lst, kont) {
            let fn helper {
                ([], lesser, greater) { kont(lesser, greater) }
                (first @ rest, lesser, greater) {
                    if (predicate(key, first) == lt) {
                        helper(rest, lesser, first @ greater)
                    } else {
                        helper(rest, first @ lesser, greater)
                    }
                }
            }
            in helper(lst, [], [])
        }
    in
        full_sort(lst)
}

// sort: list(#a) -> list(#a)
fn sort(l) { sortBy(fn (a, b) { a <=> b }, l) }