//@NO-IMPLICIT-PRELUDE
//! A dynamically sized contigous sequence.
let prim = import! std.array.prim
let int @ { ? } = import! std.int
let { (++) } = import! std.string
let prelude @ { Num, Eq, Ord, Show, Functor, (<), (==), (/=), (-), (+) } = import! std.prelude
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
{
eq,
ord,
show,
functor,
foldable,
traversable,
semigroup,
monoid,
is_empty,
..
prim
}