prelude.e1

type Maybe a = Some { value : a } | None

class Conv a b {
 $ : a -> b
}

instance Conv a String where Show a {
 $ = show
}

instance Conv Int Float {
 $ = floatOfInt
}

fst (a, b) = a
snd (a, b) = b

!= a b = !(a==b)

class IsString t { theString : t -> String }
instance IsString String { theString s = s }

print x = static if IsString x then puts (theString x) else puts (show x)

println x = do
  print x
  puts "\n"

instance Show (Maybe a) where Show a {
  show (Some x) = "Some " ~ show x
  show None     = "None"
}

type Result t e = Ok { value: t } | Err { error: e }

instance Conv (Result t e) (Maybe t) {
  $ (Ok x)  = Some x
  $ (Err e) = None
}

class OrElse m -> a {
  ?? : m -> a -> a
}

instance OrElse (Maybe t) t {
  ?? (Some x) v = x
  ?? None     v = v
}

instance OrElse (Result t e) t {
  ?? (Ok x)  v = x
  ?? (Err _) v = v
}

class Iterator it -> a {
  next : it -> Maybe a
}

type IotaIter {
  mut cur : Int
  end : Int
}

instance Iterator IotaIter Int {
  next it =
    if it.cur < it.end then do
      x = it.cur
      it.cur := x + 1
      Some x
    else None
}

iota n = IotaIter 0 n

type ArrayIter c {
  arr : c
  mut pos : Int
}

instance Iterator (ArrayIter (Vector e)) e {
  next it =
    if it.pos < length it.arr then do
      x = it.arr[it.pos]
      it.pos := it.pos + 1
      Some x
    else None
}

instance Iterator (ArrayIter (Array e)) e {
  next it =
    if it.pos < length it.arr then do
      x = it.arr[it.pos]
      it.pos := it.pos + 1
      Some x
    else None
}

class Sequence s -> e it where Iterator it e {
  getIterator : s -> it
}

instance Sequence (Vector t) t (ArrayIter (Vector t)) {
  getIterator arr = ArrayIter arr 0
}

instance Sequence (Array t) t (ArrayIter (Array t)) {
  getIterator arr = ArrayIter arr 0
}

instance Sequence t e t where Iterator t e  {
  getIterator it = it
}

type Filter iter e {
  orig : iter
  pred : e -> Bool
}

instance Iterator (Filter r e) e where Iterator r e {
  next f =
    match (next f.orig) {
      | None => None
      | (Some x) => if f.pred x then Some x else next f
    }
}

filter : (elt -> Bool) -> seq -> Filter it elt where Sequence seq elt it
filter p seq = Filter (getIterator seq) p


type MapResult iter a b {
  orig : iter
  func : a -> b
}

instance Iterator (MapResult r a b) b where Iterator r a {
  next m =
    match (next m.orig) {
      | None => None
      | (Some x) => Some (m.func x)
    }
}

map : (a -> b) -> seq -> MapResult it a b where Sequence seq a it
map f seq = MapResult (getIterator seq) f

instance HasLength (MapResult r a b) where HasLength r {
  length m = length m.orig
}

instance HasLength (ArrayIter (Vector e)) {
  length it = length it.arr
}

instance HasLength IotaIter {
  length it = it.end - it.cur
}

instance OpIndex IotaIter Int Int {
  opIndex iot idx = iot.cur + idx
}

instance OpIndex (MapResult r a b) Int b where OpIndex r Int a {
  opIndex m i = m.func m.orig[i]
}

instance OpIndex (ArrayIter (Vector e)) Int e {
  opIndex it i = it.arr[it.pos + i]
}

eachIter f it =
  match (next it) {
    | (Some x) => {f x; eachIter f it}
    | None   => ()
  }

each f xs = eachIter f (getIterator xs)

instance Conv Int Int { $ x = x }

sumIt it s =
  match (next it) {
    | None => s
    | (Some x) => sumIt it (s+x)
  }

sum xs = sumIt (getIterator xs) $0

max a b = if a > b then a else b
min a b = if a < b then a else b

showIt it notFirst =
  match (next it) {
    | None => "]"
    | (Some x) => (if notFirst then ", " ~ show x else show x) ~ showIt it True
  }

showSeq xs = "[" ~ showIt (getIterator xs) False
instance Show (Vector a) where Show a { show = showSeq }
instance Show (Array  a) where Show a { show = showSeq }

type Buf a {
  mut buf : Array a
  mut count : Int
}

arrToVec xs = makeVector (length xs) { i => xs[i] }

vecToArr xs = makeArray  (length xs) { i => xs[i] }

newBuf x = Buf (makeArray 1 {i => x}) 1

addToBuf b x = do
  len = length b.buf
  if b.count == len then
    b.buf := makeArray (len * 2) { i => if i < len then b.buf[i] else x }
  b.buf[b.count] := x
  b.count := b.count + 1

iterToBuf : it -> Buf a where Iterator it a
iterToBuf it = do
  loop buff =
    match (next it) {
      | (Some x) => {addToBuf buff x; loop buff}
      | None => buff
    }

  match (next it) {
    | (Some x) => loop (newBuf x)
    | None => Buf (vecToArr []) 0
  }

toVector : it -> Vector a where Iterator it a
toVector it = do
  buff = iterToBuf it
  makeVector (buff.count) {i => buff.buf[i]}

toArray : it -> Array a where Iterator it a
toArray it = do
  buff = iterToBuf it
  makeArray buff.count { i => buff.buf[i] }

eqVec xs ys = do
  n = length xs
  if n != length ys then False else do
    loop i =
      if i >= n then True else
        if xs[i] != ys[i] then False else loop (i+1)
    loop 0

instance Eq (Vector a) where Eq a { == = eqVec }
instance Eq (Array a)  where Eq a { == = eqVec }

type Flatten itOfIt it {
  org : itOfIt
  mut cur : Maybe it
}

instance Iterator (Flatten it of) e where Iterator of e, Iterator it of {
  next fl =
    match fl.cur {
      | (Some xs) => match (next xs) {
          | (Some x) => Some x
          | None => { fl.cur := next fl.org; next fl }
          }
      | None => None
    }
}

flatten xss = Flatten xss (next xss)

type FilterMaybe iter { it : iter }

instance Iterator (FilterMaybe iter) e where Iterator iter (Maybe e) {
  next fm =
    match (next fm.it) {
      | (Some (Some x)) => Some x
      | (Some None) => next fm
      | None => None
    }
}

filterMaybe it = FilterMaybe it


anyIt f it = match (next it) { | (Some x) => if f x then True else anyIt f it | None => False }

any f xs = anyIt f (getIterator xs)