//@NO-IMPLICIT-PRELUDE
//! A dynamically sized contigous sequence.

let prim @ { Array } = import! std.array.prim
let int @ { ? } = import! std.int
let { (++) } = import! std.string
let { Num, (-), (+) } = import! std.num
let { Eq, Ord, (<), (==), (/=) } = import! std.cmp
let { Show } = import! std.show
let { Functor } = import! std.functor
let { Bool, Ordering, compare, min } = import! std.cmp
let { Foldable } = import! std.foldable
let { Traversable } = import! std.traversable
let { Semigroup } = import! std.semigroup
let { Monoid } = import! std.monoid

// FIXME Implement the functions using this in Rust so we don't have quadratic complexity for `map` etc
let cons l r = prim.append [l] r

let eq ?eq : [Eq a] -> Eq (Array a) =
    let array_eq l r =
        if prim.len l /= prim.len r then False
        else
            let len = prim.len l
            rec let array_eq_ i =
                if i < len then
                    let x = prim.index l i
                    let y = prim.index r i
                    eq.(==) x y && array_eq_ (i + 1)
                else True
            array_eq_ 0
    { (==) = array_eq }

let ord ?ord : [Ord a] -> Ord (Array a) =
    let array_cmp l r =
        let min_len = min (prim.len l) (prim.len r)
        rec let array_cmp_ i =
            if i < min_len then
                let x = prim.index l i
                let y = prim.index r i
                match ord.compare x y with
                | EQ -> array_cmp_ (i + 1)
                | o -> o
            else compare (prim.len l) (prim.len r)

        array_cmp_ 0
    { eq, compare = array_cmp }

let show ?d : [Show a] -> Show (Array a) =
    let show xs =
        let len = prim.len xs
        if len == 0 then "[]"
        else
            rec let show_elems i =
                if i < len then
                    let x = prim.index xs i
                    ", " ++ d.show x ++ show_elems (i + 1)
                else ""

            "[" ++ d.show (prim.index xs 0) ++ show_elems 1 ++ "]"
    { show }

let functor : Functor Array =
    let map f xs =
        rec let map_ i =
            if i < prim.len xs then
                let y = prim.index xs i
                cons (f y) (map_ (i + 1))
            else []
        map_ 0
    { map }

let foldable : Foldable Array =
    let foldr f y xs =
        let len = prim.len xs
        rec let foldr_ i y =
            if i == 0 then y
            else
                let x = prim.index xs (i - 1)
                foldr_ (i - 1) (f x y)
        foldr_ len y

    let foldl f y xs =
        let len = prim.len xs
        rec let foldl_ i y =
            if i < len then
                let x = prim.index xs i
                foldl_ (i + 1) (f y x)
            else y

        foldl_ 0 y

    { foldr, foldl }

let traversable : Traversable Array =
    {
        functor,
        foldable,
        traverse = \app f ->
            foldable.foldr
                (\a b -> app.apply (app.functor.map cons (f a)) b)
                (app.wrap []),
    }

let semigroup : Semigroup (Array a) = { append = prim.append }
let monoid : Monoid (Array a) = { semigroup, empty = [] }

let is_empty array = prim.len array == 0

{
    Array,

    eq,
    ord,
    show,
    functor,
    foldable,
    traversable,
    semigroup,
    monoid,
    is_empty,
    ..
    prim
}