Iter.fold

--
-- Base Definitions
--


type Either a b = Left a | Right b

def (opt ? default) =
  case opt
  | Some x -> x
  | None -> default
  end

def (f << g) = x -> f (g x)
def (g >> f) = x -> f (g x)


-- Iterators

type Iter a = Iter :: (s, s -> (a, s)?) -> Iter a


type Self a = Iter a


val empty =
  Iter ((), -> None)


def count () =
  Iter (0, i -> Some (i, i + 1))


def range by: (step = 1) start stop =
  let next i =
    if i >= stop then None
    else Some (i, i + step)
  in
    Iter (start, next)


def iota by: (step = 1) stop =
  range by: step stop


def ^n = iota stop


def repeat x =
  Iter ((), -> Some (x, ()))


def repeatedly f =
  Iter ((), -> Some (f (), ()))


def iterate f x =
  Iter (x, x -> Some (x, f x))


def init n f =
  let next i =
    if i = n then None
    else Some (f i, i + 1)
  in
    Iter (0, next)


def view (Iter (s0, next)) =
  case next s0
  | Some (a, s1) -> Some (a, Iter (s1, next))
  | None -> None
  end



def append (Iter (s0, next)) a =
  let next' (s, is_done) =
    if is_done then None
    else
      case next s
      | None         -> Some (a, (s, True))
      | Some (a, s') -> Some (a, (s', is_done))
      end
  in
    Iter ((s0, False), next')


def prepend (Iter (s0, next)) x =
  let next' (s, opt) =
    case opt
    | Some x ->
      case next s
      | Some (a, s') -> Some (x, (s', Some a))
      | None         -> Some (x, (s,  None))
      end
    | None -> None
    end
  in
    Iter ((s0, Some x), next')


val zero = empty


def one a =
  Iter (False, False -> Some (a, true) | True -> None)


def two a b =
  append (one a) b


def three a b c =
  append (two a b) c


def fold f r0 (Iter (s0, next)) =
  let loop r s =
    case next s
    | None -> r
    | Some (a, s') -> loop (f r a) s'
    end
  in
    loop r0 s0


def fold_while f r0 (Iter (s0, next)) =
  let loop r s =
    case next s
    | Some (a, s') ->
      case f r a
      | `Continue r' -> loop r' s'
      | `Done r' -> r'
      end
    | None -> r
    end
  in
    loop r0 s0


def reduce f iter =
  case view iter
  | Some (a, iter') -> Some (fold f a iter')
  | None -> None
  end


def fold_right f (Iter (s0, next)) r0 =
  let loop r s =
    case next s
    | None -> r
    | Some (a, s') -> f a (loop r s')
    end
  in
    loop r0 s0


let all p self =
  fold_while
    (r a -> if not (p a) then `Done False
            else `Continue r)
    True
    self


let any p self =
  fold_while
    (r a -> if p a then `Done True
            else `Continue r)
    False
    self


def concat (Iter s0_a next_a) (Iter s0_b next_b) =
  let next' (Left s_a) =
      case next_a s_a
      | Some (a, s_a') -> Some (a, Left s_a')
      | None ->
        case next_b s0_b
        | Some (b, s_b') -> Some (b, Right s_b')
        | None -> None
        end
      end
    | next' (Right s_b) =
      case next_b s_b
      | Some (b, s_b') -> Some (b, Right s_b')
      | None -> None
      end
  in
    Iter (Left s0_a, next')


def chain list =
  let loop r [x, xs...] = loop (concat r x) xs
    | loop r [] = r
  in
    case list
    | [] -> empty
    | [x, xs...] -> loop x xs
    end


def chunks n self =
  undefined


def compare f self other =
  undefined


let compress self selector =
  undefined


let contains x self =
  fold_while
    (r a -> if a == x then `Done True
            else `Continue r)
    false
    self


def cycle (Iter (s0, next)) =
  let next' s =
    case next s
    | None -> next s0
    | some -> some
    end
  in
    Iter (s0, next')


let dedup ?by iter =
  undefined


def drop n (Iter (s0, next)) =
  let next' (s, i) =
    let loop s i =
      case next s
      | Some (_, s') if i == 0 -> Some (a, (s', i))
      | Some (_, s') -> loop s' (i - 1)
      | None -> None
      end
    in
      loop s i
  in
    Iter ((s0, n), next')


def drop_while p (Iter (s0, next)) =
  let next' (s, dropping) =
    let loop s =
      case next s
      | Some (a, s') if p a && dropping -> loop s'
      | Some (a, s') -> Some (a, (s', False))
      | None -> None
      end
    in
      loop s
  in
    Iter ((s0, True), next')


def each f = fold (() a -> f a) ()


def ends_with target self =
  undefined


def enumerate from: (start = 0) (Iter (s0, next)) =
  let next' (s, i) =
    case next s
    | Some (a, s') -> Some ((i, a), (s', i + 1))
    | None -> None
    end
  in
    Iter ((s0, start), next')


def equal f self other =
  undefined


def filter p (Iter (s0, next)) =
  let next' s =
    let loop s =
      case next s
      | Some (a, s') if p a -> Some (a, s')
      | Some (_, s') -> loop s'
      | None -> None
      end
    in
      loop s
  in
    Iter (s0, next')


def map f (Iter (s0, next)) =
  let next' s =
    case next s
    | Some (a, s') -> Some (f a, s')
    | None -> None
    end
  in
    Iter (s0, next')


def filter_map f (Iter (s0, next)) =
  let next' s =
    let loop s =
      case next s
      | Some (a, s') ->
        case f a
        | Some b -> Some (b, s')
        | None -> loop s'
        end
      | None -> None
      end
    in
      loop s
  in
    Iter (s0, next')


def find p =
  fold_while
    (r a -> if p a then `Done (Some a)
            else `Continue r)
    None


def find_index p =
  enumerate >> fold_while
    (r (i, a) -> if p a then `Done (Some i)
                 else `Continue r)
    None


def find_indices p self =
  self
  |> enumerate
  |> filter (fun (i, a) -> p a)
  |> map    (fun (i, a) -> i)


def flat_map f self =
  undefined


def flatten self =
  undefined


def group self =
  undefined


def group_by p (Iter (s0, next)) =
  let next' (s, g0, is_done) =
    if is_done then None
    else
      let loop g s =
        case (g, next s)
        | ([]         , Some (a, s'))             -> loop [a]       s'
        | ([last, ...], Some (a, s')) if p last a -> loop [a, g...] s'
        | ([_   , ...], Some (a, s'))             -> Some (List.rev g, (s', [a], is_done))
        | ([_   , ...], None)                     -> Some (List.rev g, (s , [] , True))
        | ([]         , None)                     -> None
        end
      in
        loop g0 s
  in
    Iter ((s0, [], False), next')


def group_on f =
  group_by (a b -> f a == f b)


def head (Iter (s0, next)) =
  case next s0
  | Some (x, _) -> Some x
  | None -> None
  end


def index x =
  find_index ((==) x)


let indices x iter =
  find_indices ((=) x) iter


let intersparse iter x = failwith "todo"


def is_empty (Iter (s0, next)) =
  case next s0
  | Some _ -> False
  | None   -> True
  end


let join sep iter     = failwith "todo"


let merge f iter iter = failwith "todo"


def last =
  fold (_ a -> Some a) None


let len self =
  fold (fun r _ -> r + 1) 0 self

let max ?by iter =
  let cmp = by // Pervasives.compare in
  let max' x y =
    match cmp x y with
    | 1 -> x
    | _ -> y in
  reduce max' iter

let min ?by iter =
  let cmp = by // Pervasives.compare in
  let min' x y =
    match cmp x y with
    | -1 -> x
    | _  -> y in
  reduce min' iter

let nth n iter =
  fold (fun r (i, a) -> if i = n then Some a else r)
    None (enumerate iter)

let pairwise iter               = failwith "todo"
let partition p iter            = failwith "todo"
let powerset iter               = failwith "todo"
let product iter                = failwith "todo"

let reject p iter =
  filter (not << p) iter

let remove ?(eq = (=)) x (Iter (s0, next)) =
  let next' s =
    match next s with
    | Some (a, s') when eq a x -> next s'
    | original -> original in
  Iter (s0, next')

let remove_at i iter            = failwith "todo"

let reverse iter                = failwith "todo"
let scan f z iter               = failwith "todo"
let scan_right f z iter         = failwith "todo"
let slice iter n m              = failwith "todo"
let sort iter                   = failwith "todo"
let sort_by f iter              = failwith "todo"
let sort_on f iter              = failwith "todo"
let starts_with target iter     = failwith "todo"
let split_at i iter             = failwith "todo"
let split_while p iter          = failwith "todo"

let sum iter =
  fold (+) 0 iter

let tail (Iter (s0, next)) =
  let next' (s, did_skip_head) =
    match next s with
    | Some (a, s1) when did_skip_head -> Some (a, (s1, did_skip_head))
    | Some (_, s1) ->
      begin match next s1 with
        | Some (a, s2) -> Some (a, (s2, true))
        | None -> None
      end
    | None -> None in
  Iter ((s0, false), next')

let take n (Iter (s0, next)) =
  let next' (s, i) =
    if i <= 0 then None
    else match next s with
      | Some (a, s') -> Some (a, (s', i - 1))
      | None -> None in
  Iter ((s0, n), next')

let take_every n iter =
  iter
  |> enumerate
  |> filter (fun (i, _) -> i mod n = 0)
  |> map    (fun (_, a) -> a)

let take_while p iter           = failwith "todo"
let take_last n iter            = failwith "todo"

let to_list self =
  List.rev (fold (fun acc x -> x :: acc) [] self)

let collect = to_list

let of_list l =
  let next = function
    | []    -> None
    | x::xs -> Some (x, xs) in
  Iter (l, next)

let iter = of_list

let unzip iter            = failwith "todo"
let uniq iter             = failwith "todo"
let uniq_by f iter        = failwith "todo"
let zip iter iter         = failwith "todo"
let zip_with f iter iter  = failwith "todo"


module Input = struct
  module type Sig0 = sig
    type t
    type item
    val iter : t -> item iter
  end

  module type Sig1 = sig
    type 'a t
    val iter : 'a t -> 'a iter
  end


  module type Ext0 = sig
    type t
    type item

    val all          : (item -> bool) -> t -> bool
    val any          : (item -> bool) -> t -> bool
    val chain        : t list -> item iter
    val chunks       : int -> t -> item iter iter
    val compare      : (item -> item -> int) -> t -> t -> int
    val contains     : item -> t -> bool
    val cycle        : t -> item iter
    val dedup        : ?by: (item -> item -> bool) -> t -> item iter
    val drop         : int -> t -> item iter
    val drop_while   : (item -> bool) -> t -> item iter
    val each         : (item -> unit) -> t -> unit
    val ends_with    : t -> t -> bool
    val enumerate    : ?from: int -> t -> (int * item) iter
    val equal        : (item -> item -> bool) -> t -> t -> bool
    val filter       : (item -> bool) -> t -> item iter
    val filter_map   : (item -> 'b option) -> t -> 'b iter
    val find         : (item -> bool) -> t -> item option
    val find_index   : (item -> bool) -> t ->  int option
    val find_indices : (item -> bool) -> t -> int iter
    val fold         : ('r -> item -> 'r) -> 'r -> t -> 'r
    val fold_while   : ('r -> item -> [ `Continue of 'r | `Done of 'r ]) -> 'r -> t -> 'r
    val fold_right   : (item -> 'r -> 'r) -> t -> 'r -> 'r
    val group        : t -> item list iter
    val group_by     : (item -> item -> bool) -> t -> item list iter
    val group_on     : (item -> 'b) -> t -> item list iter
    val head         : t -> item option
    val index        : item -> t -> int option
    val indices      : item -> t -> int iter
    val intersparse  : t -> item -> item iter
    val is_empty     : t -> bool
    val join         : string -> t -> string
    val merge        : (item -> item -> 'a option) -> t -> t -> 'a iter
    val last         : t -> item option
    val len          : t -> int
    val map          : (item -> 'b) -> t -> 'b iter
    val max          : ?by:(item -> item -> int) -> t -> item option
    val min          : ?by:(item -> item -> int) -> t -> item option
    val nth          : int -> t -> item option
    val pairwise     : t -> (item * item) iter
    val partition    : (item -> bool) -> t -> item iter * item iter
    val powerset     : t -> item iter iter
    val product      : t -> int
    val reduce       : (item -> item -> item) -> t -> item option
    val reject       : (item -> bool) -> t -> item iter
    val reverse      : t -> item iter
    val scan         : ('r -> item -> 'r) -> 'r -> t -> 'r iter
    val scan_right   : ('r -> item -> 'r) -> 'r -> t -> 'r iter
    val slice        : t -> int -> int -> item iter
    val sort         : t -> item iter
    val sort_by      : (item -> item -> int) -> t -> item iter
    val sort_on      : (item -> 'b) -> t -> item iter
    val starts_with  : t -> t -> bool
    val split_at     : int -> t -> item iter * item iter
    val split_while  : (item -> bool) -> t -> item iter * item iter
    val sum          : t -> int
    val tail         : t -> item iter
    val take         : int -> t -> item iter
    val take_every   : int -> t -> item iter
    val take_while   : (item -> bool) -> t -> item iter
    val take_last    : int -> t -> item iter
    val to_list      : t -> item list
    val uniq         : t -> item iter
    val uniq_by      : (item -> item -> bool) -> t -> item iter
    val zip          : t -> t -> (item * item) iter
    val zip_with     : (item -> item -> 'a) -> t -> t -> 'a iter
  end

  module type Ext1 = sig
    type 'a t

    val all          : ('a -> bool) -> 'a t -> bool
    val any          : ('a -> bool) -> 'a t -> bool
    val concat       : 'a t -> 'a t -> 'a iter
    val chain        : 'a t list -> 'a iter
    val chunks       : int -> 'a t -> 'a iter iter
    val compare      : ('a -> 'a -> int) -> 'a t -> 'a t -> int
    val compress     : 'a t -> bool t -> 'a iter
    val contains     : 'a -> 'a t -> bool
    val cycle        : 'a t -> 'a iter
    val dedup        : ?by: ('a -> 'a -> bool) -> 'a t -> 'a iter
    val drop         : int -> 'a t -> 'a iter
    val drop_while   : ('a -> bool) -> 'a t -> 'a iter
    val each         : ('a -> unit) -> 'a t -> unit
    val ends_with    : 'a t -> 'a t -> bool
    val enumerate    : ?from: int -> 'a t -> (int * 'a) iter
    val equal        : ('a -> 'a -> bool) -> 'a t -> 'a t -> bool
    val filter       : ('a -> bool) -> 'a t -> 'a iter
    val filter_map   : ('a -> 'b option) -> 'a t -> 'b iter
    val find         : ('a -> bool) -> 'a t -> 'a option
    val find_index   : ('a -> bool) -> 'a t ->  int option
    val find_indices : ('a -> bool) -> 'a t -> int iter
    val flat_map     : ('a -> 'b t) -> 'a t -> 'b iter
    val flatten      : 'a t t -> 'a iter
    val fold         : ('r -> 'a -> 'r) -> 'r -> 'a t -> 'r
    val fold_while   : ('r -> 'a -> [ `Continue of 'r | `Done of 'r ]) -> 'r -> 'a t -> 'r
    val fold_right   : ('a -> 'r -> 'r) -> 'a t -> 'r -> 'r
    val group        : 'a t -> 'a list iter
    val group_by     : ('a -> 'a -> bool) -> 'a t -> 'a list iter
    val group_on     : ('a -> 'b) -> 'a t -> 'a list iter
    val head         : 'a t -> 'a option
    val index        : 'a -> 'a t -> int option
    val indices      : 'a -> 'a t -> int iter
    val intersparse  : 'a t -> 'a -> 'a iter
    val is_empty     : 'a t -> bool
    val join         : string -> string t -> string
    val merge        : ('a -> 'b -> 'c option) -> 'a t -> 'b t -> 'c iter
    val last         : 'a t -> 'a option
    val len          : 'a t -> int
    val map          : ('a -> 'b) -> 'a t -> 'b iter
    val max          : ?by:('a -> 'a -> int) -> 'a t -> 'a option
    val min          : ?by:('a -> 'a -> int) -> 'a t -> 'a option
    val nth          : int -> 'a t -> 'a option
    val pairwise     : 'a t -> ('a * 'a) iter
    val partition    : ('a -> bool) -> 'a t -> 'a iter * 'a iter
    val powerset     : 'a t -> 'a iter iter
    val product      : int t -> int
    val reduce       : ('a -> 'a -> 'a) -> 'a t -> 'a option
    val reject       : ('a -> bool) -> 'a t -> 'a iter
    val reverse      : 'a t -> 'a iter
    val scan         : ('r -> 'a -> 'r) -> 'r -> 'a t -> 'r iter
    val scan_right   : ('r -> 'a -> 'r) -> 'r -> 'a t -> 'r iter
    val slice        : 'a t -> int -> int -> 'a iter
    val sort         : 'a t -> 'a iter
    val sort_by      : ('a -> 'a -> int) -> 'a t -> 'a iter
    val sort_on      : ('a -> 'b) -> 'a t -> 'a iter
    val starts_with  : 'a t -> 'a t -> bool
    val split_at     : int -> 'a t -> 'a iter * 'a iter
    val split_while  : ('a -> bool) -> 'a t -> 'a iter * 'a iter
    val sum          : int t -> int
    val tail         : 'a t -> 'a iter
    val take         : int -> 'a t -> 'a iter
    val take_every   : int -> 'a t -> 'a iter
    val take_while   : ('a -> bool) -> 'a t -> 'a iter
    val take_last    : int -> 'a t -> 'a iter
    val to_list      : 'a t -> 'a list
    val unzip        : ('a * 'b) t -> 'a iter * 'b iter
    val uniq         : 'a t -> 'a iter
    val uniq_by      : ('a -> 'a -> bool) -> 'a t -> 'a iter
    val zip          : 'a t -> 'b t -> ('a * 'b) iter
    val zip_with     : ('a -> 'b -> 'c) -> 'a t -> 'b t -> 'c iter
  end


  module Make0(M : Sig0) : (Ext0 with type    t := M.t
                                  and type item := M.item) = struct
    let all p iterable                  = all p (M.iter iterable)
    let any p iterable                  = any p (M.iter iterable)
    let concat iterable1 iterable2      = concat (M.iter iterable1) (M.iter iterable2)
    let chain iterables                 = chain (List.map M.iter iterables)
    let chunks size iterable            = chunks size (M.iter iterable)
    let compare cmp iterable1 iterable2 = compare cmp (M.iter iterable1) (M.iter iterable2)
    let map f iterable                  = map f (M.iter iterable)
    let contains x iterable             = contains x (M.iter iterable)
    let cycle iterable                  = cycle (M.iter iterable)
    let dedup ?by iterable              = dedup ?by (M.iter iterable)
    let drop n iterable                 = drop n (M.iter iterable)
    let drop_while p iterable           = drop_while p (M.iter iterable)
    let each f iterable                 = each f (M.iter iterable)
    let ends_with end_iterable iterable = ends_with (M.iter end_iterable) (M.iter iterable)
    let enumerate ?from iterable        = enumerate ?from (M.iter iterable)
    let equal eq iterable1 iterable2    = equal eq (M.iter iterable1) (M.iter iterable2)
    let filter p iterable               = filter p (M.iter iterable)
    let filter_map p iterable           = filter_map p (M.iter iterable)
    let find p iterable                 = find p (M.iter iterable)
    let find_index p iterable           = find_index p (M.iter iterable)
    let find_indices p iterable         = find_indices p (M.iter iterable)
    let flat_map f iterable             = failwith "todo"
    let fold f z iterable               = fold f z (M.iter iterable)
    let fold_while f z iterable         = fold_while f z (M.iter iterable)
    let fold_right f iterable z         = fold_right f (M.iter iterable) z
    let group iterable                  = group (M.iter iterable)
    let group_by f iterable             = group_by f (M.iter iterable)
    let group_on f iterable             = group_on f (M.iter iterable)
    let head iterable                   = head (M.iter iterable)
    let index x iterable                = index x (M.iter iterable)
    let indices x iterable              = indices x (M.iter iterable)
    let intersparse iterable x          = intersparse (M.iter iterable) x
    let is_empty iterable               = is_empty (M.iter iterable)
    let join sep iterable               = failwith "todo"
    let merge f iterable1 iterable2     = merge f (M.iter iterable1) (M.iter iterable2)
    let last iterable                   = last (M.iter iterable)
    let len iterable                    = len (M.iter iterable)
    let max ?by iterable                = max ?by (M.iter iterable)
    let min ?by iterable                = min ?by (M.iter iterable)
    let nth n iterable                  = nth n (M.iter iterable)
    let pairwise iterable               = pairwise (M.iter iterable)
    let partition p iterable            = partition p (M.iter iterable)
    let powerset iterable               = powerset (M.iter iterable)
    let product iterable                = failwith "todo"
    let reduce f iterable               = reduce f (M.iter iterable)
    let reject p iterable               = reject p (M.iter iterable)
    let reverse iterable                = reverse (M.iter iterable)
    let scan f z iterable               = scan f z (M.iter iterable)
    let scan_right f z iterable         = scan_right f z (M.iter iterable)
    let slice iterable n m              = slice (M.iter iterable) n m
    let sort iterable                   = sort (M.iter iterable)
    let sort_by f iterable              = sort_by f (M.iter iterable)
    let sort_on f iterable              = sort_on f (M.iter iterable)
    let starts_with start iterable      = starts_with (M.iter start) (M.iter iterable)
    let split_at i iterable             = split_at i (M.iter iterable)
    let split_while p iterable          = split_while p (M.iter iterable)
    let sum iterable                    = failwith "todo"
    let tail iterable                   = tail (M.iter iterable)
    let take n iterable                 = take n (M.iter iterable)
    let take_every n iterable           = take_every n (M.iter iterable)
    let take_while p iterable           = take_while p (M.iter iterable)
    let take_last n iterable            = take_last n (M.iter iterable)
    let to_list iterable                = to_list (M.iter iterable)
    let uniq iterable                   = uniq (M.iter iterable)
    let uniq_by f iterable              = uniq_by f (M.iter iterable)
    let zip iterable1 iterable2         = zip (M.iter iterable1) (M.iter iterable2)
    let zip_with f iterable1 iterable2  = zip_with f (M.iter iterable1) (M.iter iterable2)

  end


  module Make1(M : Sig1) : (Ext1 with type 'a t := 'a M.t) = struct
    let all p iterable                  = all p (M.iter iterable)
    let any p iterable                  = any p (M.iter iterable)
    let concat iterable1 iterable2      = concat (M.iter iterable1) (M.iter iterable2)
    let chain iterables                 = chain (List.map M.iter iterables)
    let chunks size iterable            = chunks size (M.iter iterable)
    let compare cmp iterable1 iterable2 = compare cmp (M.iter iterable1) (M.iter iterable2)
    let compress iterable selector      = compress (M.iter iterable) (M.iter selector)
    let map f iterable                  = map f (M.iter iterable)
    let contains x iterable             = contains x (M.iter iterable)
    let cycle iterable                  = cycle (M.iter iterable)
    let dedup ?by iterable              = dedup ?by (M.iter iterable)
    let drop n iterable                 = drop n (M.iter iterable)
    let drop_while p iterable           = drop_while p (M.iter iterable)
    let each f iterable                 = each f (M.iter iterable)
    let ends_with end_iterable iterable = ends_with (M.iter end_iterable) (M.iter iterable)
    let enumerate ?from iterable        = enumerate ?from (M.iter iterable)
    let equal eq iterable1 iterable2    = equal eq (M.iter iterable1) (M.iter iterable2)
    let filter p iterable               = filter p (M.iter iterable)
    let filter_map p iterable           = filter_map p (M.iter iterable)
    let find p iterable                 = find p (M.iter iterable)
    let find_index p iterable           = find_index p (M.iter iterable)
    let find_indices p iterable         = find_indices p (M.iter iterable)
    let flat_map f iterable             = failwith "todo"
    let flatten iterable                = flatten (map M.iter iterable)
    let fold f z iterable               = fold f z (M.iter iterable)
    let fold_while f z iterable         = fold_while f z (M.iter iterable)
    let fold_right f iterable z         = fold_right f (M.iter iterable) z
    let group iterable                  = group (M.iter iterable)
    let group_by f iterable             = group_by f (M.iter iterable)
    let group_on f iterable             = group_on f (M.iter iterable)
    let head iterable                   = head (M.iter iterable)
    let index x iterable                = index x (M.iter iterable)
    let indices x iterable              = indices x (M.iter iterable)
    let intersparse iterable x          = intersparse (M.iter iterable) x
    let is_empty iterable               = is_empty (M.iter iterable)
    let join sep iterable               = join sep (M.iter iterable)
    let merge f iterable1 iterable2     = merge f (M.iter iterable1) (M.iter iterable2)
    let last iterable                   = last (M.iter iterable)
    let len iterable                    = len (M.iter iterable)
    let max ?by iterable                = max ?by (M.iter iterable)
    let min ?by iterable                = min ?by (M.iter iterable)
    let nth n iterable                  = nth n (M.iter iterable)
    let pairwise iterable               = pairwise (M.iter iterable)
    let partition p iterable            = partition p (M.iter iterable)
    let powerset iterable               = powerset (M.iter iterable)
    let product iterable                = product (M.iter iterable)
    let reduce f iterable               = reduce f (M.iter iterable)
    let reject p iterable               = reject p (M.iter iterable)
    let reverse iterable                = reverse (M.iter iterable)
    let scan f z iterable               = scan f z (M.iter iterable)
    let scan_right f z iterable         = scan_right f z (M.iter iterable)
    let slice iterable n m              = slice (M.iter iterable) n m
    let sort iterable                   = sort (M.iter iterable)
    let sort_by f iterable              = sort_by f (M.iter iterable)
    let sort_on f iterable              = sort_on f (M.iter iterable)
    let starts_with start iterable      = starts_with (M.iter start) (M.iter iterable)
    let split_at i iterable             = split_at i (M.iter iterable)
    let split_while p iterable          = split_while p (M.iter iterable)
    let sum iterable                    = sum (M.iter iterable)
    let tail iterable                   = tail (M.iter iterable)
    let take n iterable                 = take n (M.iter iterable)
    let take_every n iterable           = take_every n (M.iter iterable)
    let take_while p iterable           = take_while p (M.iter iterable)
    let take_last n iterable            = take_last n (M.iter iterable)
    let to_list iterable                = to_list (M.iter iterable)
    let unzip iterable                  = unzip (M.iter iterable)
    let uniq iterable                   = uniq (M.iter iterable)
    let uniq_by f iterable              = uniq_by f (M.iter iterable)
    let zip iterable1 iterable2         = zip (M.iter iterable1) (M.iter iterable2)
    let zip_with f iterable1 iterable2  = zip_with f (M.iter iterable1) (M.iter iterable2)
  end

  module type Sig = Sig1
  module type Ext = Ext1

  module Make = Make1
end

module Index = struct
  module type Sig1 = sig
    type 'a t

    val len : 'a t -> int
    val idx : 'a t -> int -> 'a
  end

  module type Ext1 = sig
    type 'a t

    include Input.Sig1 with type 'a t := 'a t
    include Input.Ext1 with type 'a t := 'a t

    val len : 'a t -> int
    val get    : 'a t -> int -> 'a option
    val last   : 'a t -> 'a option
    val slice  : 'a t -> int -> int -> 'a iter
    val each  : ('a -> unit) -> 'a t -> unit
  end

  module Make1(M : Sig1) : (Ext1 with type 'a t := 'a M.t) = struct

    let iter indexable =
      let len = M.len indexable in
      let next i =
        if i >= len then None
        else Some (M.idx indexable i, i + 1) in
      Iter (0, next)

    include Input.Make(struct
        type 'a t = 'a M.t
        let iter = iter
      end)

    let each f indexable =
      let len = M.len indexable in
      let rec loop i =
        if i = len then ()
        else (f (M.idx indexable i); loop (i + 1)) in
      loop 0

    let len = M.len

    let get indexable i =
      let len = M.len indexable in
      let i = if i < 0 then len + i else i in
      if i < 0 || i >= len then None
      else Some (M.idx indexable i)

    let last indexable =
      let len = M.len indexable in
      if len <= 0 then None
      else Some (M.idx indexable (len - 1))

    let slice indexable n m =
      failwith "todo"
  end

  module type Sig = Sig1
  module type Ext = Ext1

  module Make = Make1
end