sig
  type 'a monoid = { zero : 'a; combine : '-> '-> 'a; }
  exception Empty
  module type S =
    sig
      type ('a, 'b) fg
      type ('a, 'b, 'c) wrap
      val empty : ('a, 'b) BatFingerTree.S.fg
      val singleton : '-> ('a, 'b) BatFingerTree.S.fg
      val cons :
        (('a, 'b) BatFingerTree.S.fg -> '-> ('a, 'b) BatFingerTree.S.fg,
         'a, 'b)
        BatFingerTree.S.wrap
      val snoc :
        (('a, 'b) BatFingerTree.S.fg -> '-> ('a, 'b) BatFingerTree.S.fg,
         'a, 'b)
        BatFingerTree.S.wrap
      val front :
        (('a, 'b) BatFingerTree.S.fg ->
         (('a, 'b) BatFingerTree.S.fg * 'a) option, 'a, 'b)
        BatFingerTree.S.wrap
      val front_exn :
        (('a, 'b) BatFingerTree.S.fg -> ('a, 'b) BatFingerTree.S.fg * 'a, 'a,
         'b)
        BatFingerTree.S.wrap
      val head : ('a, 'b) BatFingerTree.S.fg -> 'a option
      val head_exn : ('a, 'b) BatFingerTree.S.fg -> 'a
      val last : ('a, 'b) BatFingerTree.S.fg -> 'a option
      val last_exn : ('a, 'b) BatFingerTree.S.fg -> 'a
      val tail :
        (('a, 'b) BatFingerTree.S.fg -> ('a, 'b) BatFingerTree.S.fg option,
         'a, 'b)
        BatFingerTree.S.wrap
      val tail_exn :
        (('a, 'b) BatFingerTree.S.fg -> ('a, 'b) BatFingerTree.S.fg, 'a, 'b)
        BatFingerTree.S.wrap
      val init :
        (('a, 'b) BatFingerTree.S.fg -> ('a, 'b) BatFingerTree.S.fg option,
         'a, 'b)
        BatFingerTree.S.wrap
      val init_exn :
        (('a, 'b) BatFingerTree.S.fg -> ('a, 'b) BatFingerTree.S.fg, 'a, 'b)
        BatFingerTree.S.wrap
      val rear :
        (('a, 'b) BatFingerTree.S.fg ->
         (('a, 'b) BatFingerTree.S.fg * 'a) option, 'a, 'b)
        BatFingerTree.S.wrap
      val rear_exn :
        (('a, 'b) BatFingerTree.S.fg -> ('a, 'b) BatFingerTree.S.fg * 'a, 'a,
         'b)
        BatFingerTree.S.wrap
      val size : ('a, 'b) BatFingerTree.S.fg -> int
      val is_empty : ('a, 'b) BatFingerTree.S.fg -> bool
      val fold_left :
        ('-> '-> 'a) -> '-> ('b, 'c) BatFingerTree.S.fg -> 'a
      val fold_right :
        ('-> '-> 'a) -> '-> ('b, 'c) BatFingerTree.S.fg -> 'a
      val iter : ('-> unit) -> ('a, 'b) BatFingerTree.S.fg -> unit
      val iter_right : ('-> unit) -> ('a, 'b) BatFingerTree.S.fg -> unit
      val compare :
        ('-> '-> int) ->
        ('a, 'b) BatFingerTree.S.fg -> ('a, 'b) BatFingerTree.S.fg -> int
      val equal :
        ('-> '-> bool) ->
        ('a, 'b) BatFingerTree.S.fg -> ('a, 'b) BatFingerTree.S.fg -> bool
      val enum : ('a, 'b) BatFingerTree.S.fg -> 'BatEnum.t
      val backwards : ('a, 'b) BatFingerTree.S.fg -> 'BatEnum.t
      val to_list : ('a, 'b) BatFingerTree.S.fg -> 'a list
      val to_list_backwards : ('a, 'b) BatFingerTree.S.fg -> 'a list
      val of_enum :
        ('BatEnum.t -> ('a, 'b) BatFingerTree.S.fg, 'a, 'b)
        BatFingerTree.S.wrap
      val of_backwards :
        ('BatEnum.t -> ('a, 'b) BatFingerTree.S.fg, 'a, 'b)
        BatFingerTree.S.wrap
      val of_list :
        ('a list -> ('a, 'b) BatFingerTree.S.fg, 'a, 'b) BatFingerTree.S.wrap
      val of_list_backwards :
        ('a list -> ('a, 'b) BatFingerTree.S.fg, 'a, 'b) BatFingerTree.S.wrap
      val map :
        (('-> 'b) ->
         ('a, 'c) BatFingerTree.S.fg -> ('b, 'c) BatFingerTree.S.fg, 'b, 'c)
        BatFingerTree.S.wrap
      val map_right :
        (('-> 'b) ->
         ('a, 'c) BatFingerTree.S.fg -> ('b, 'c) BatFingerTree.S.fg, 'b, 'c)
        BatFingerTree.S.wrap
      val append :
        (('a, 'b) BatFingerTree.S.fg ->
         ('a, 'b) BatFingerTree.S.fg -> ('a, 'b) BatFingerTree.S.fg, 'a, 'b)
        BatFingerTree.S.wrap
      val reverse :
        (('a, 'b) BatFingerTree.S.fg -> ('a, 'b) BatFingerTree.S.fg, 'a, 'b)
        BatFingerTree.S.wrap
      val print :
        ?first:string ->
        ?last:string ->
        ?sep:string ->
        ('a, 'b) BatIO.printer ->
        (('a, 'c) BatFingerTree.S.fg, 'b) BatIO.printer
    end
  module Generic :
    sig
      type ('a, 'b) fg
      type ('a, 'b, 'c) wrap = monoid:'c monoid -> measure:('-> 'c) -> 'a
      val empty : ('a, 'b) fg
      val singleton : '-> ('a, 'b) fg
      val cons : (('a, 'b) fg -> '-> ('a, 'b) fg, 'a, 'b) wrap
      val snoc : (('a, 'b) fg -> '-> ('a, 'b) fg, 'a, 'b) wrap
      val front : (('a, 'b) fg -> (('a, 'b) fg * 'a) option, 'a, 'b) wrap
      val front_exn : (('a, 'b) fg -> ('a, 'b) fg * 'a, 'a, 'b) wrap
      val head : ('a, 'b) fg -> 'a option
      val head_exn : ('a, 'b) fg -> 'a
      val last : ('a, 'b) fg -> 'a option
      val last_exn : ('a, 'b) fg -> 'a
      val tail : (('a, 'b) fg -> ('a, 'b) fg option, 'a, 'b) wrap
      val tail_exn : (('a, 'b) fg -> ('a, 'b) fg, 'a, 'b) wrap
      val init : (('a, 'b) fg -> ('a, 'b) fg option, 'a, 'b) wrap
      val init_exn : (('a, 'b) fg -> ('a, 'b) fg, 'a, 'b) wrap
      val rear : (('a, 'b) fg -> (('a, 'b) fg * 'a) option, 'a, 'b) wrap
      val rear_exn : (('a, 'b) fg -> ('a, 'b) fg * 'a, 'a, 'b) wrap
      val size : ('a, 'b) fg -> int
      val is_empty : ('a, 'b) fg -> bool
      val fold_left : ('-> '-> 'a) -> '-> ('b, 'c) fg -> 'a
      val fold_right : ('-> '-> 'a) -> '-> ('b, 'c) fg -> 'a
      val iter : ('-> unit) -> ('a, 'b) fg -> unit
      val iter_right : ('-> unit) -> ('a, 'b) fg -> unit
      val compare : ('-> '-> int) -> ('a, 'b) fg -> ('a, 'b) fg -> int
      val equal : ('-> '-> bool) -> ('a, 'b) fg -> ('a, 'b) fg -> bool
      val enum : ('a, 'b) fg -> 'BatEnum.t
      val backwards : ('a, 'b) fg -> 'BatEnum.t
      val to_list : ('a, 'b) fg -> 'a list
      val to_list_backwards : ('a, 'b) fg -> 'a list
      val of_enum : ('BatEnum.t -> ('a, 'b) fg, 'a, 'b) wrap
      val of_backwards : ('BatEnum.t -> ('a, 'b) fg, 'a, 'b) wrap
      val of_list : ('a list -> ('a, 'b) fg, 'a, 'b) wrap
      val of_list_backwards : ('a list -> ('a, 'b) fg, 'a, 'b) wrap
      val map : (('-> 'b) -> ('a, 'c) fg -> ('b, 'c) fg, 'b, 'c) wrap
      val map_right : (('-> 'b) -> ('a, 'c) fg -> ('b, 'c) fg, 'b, 'c) wrap
      val append : (('a, 'b) fg -> ('a, 'b) fg -> ('a, 'b) fg, 'a, 'b) wrap
      val reverse : (('a, 'b) fg -> ('a, 'b) fg, 'a, 'b) wrap
      val print :
        ?first:string ->
        ?last:string ->
        ?sep:string ->
        ('a, 'b) BatIO.printer -> (('a, 'c) fg, 'b) BatIO.printer
      val lookup : (('-> bool) -> ('b, 'a) fg -> 'b, 'b, 'a) wrap
      val measure : (('a, 'b) fg -> 'b, 'a, 'b) wrap
      val split :
        (('-> bool) -> ('b, 'a) fg -> ('b, 'a) fg * ('b, 'a) fg, 'b, 'a)
        wrap
    end
  type 'a t
  type ('a, 'b) fg = 'a t
  type ('a, 'b, 'c) wrap = 'a
  val empty : ('a, 'b) fg
  val singleton : '-> ('a, 'b) fg
  val cons : (('a, 'b) fg -> '-> ('a, 'b) fg, 'a, 'b) wrap
  val snoc : (('a, 'b) fg -> '-> ('a, 'b) fg, 'a, 'b) wrap
  val front : (('a, 'b) fg -> (('a, 'b) fg * 'a) option, 'a, 'b) wrap
  val front_exn : (('a, 'b) fg -> ('a, 'b) fg * 'a, 'a, 'b) wrap
  val head : ('a, 'b) fg -> 'a option
  val head_exn : ('a, 'b) fg -> 'a
  val last : ('a, 'b) fg -> 'a option
  val last_exn : ('a, 'b) fg -> 'a
  val tail : (('a, 'b) fg -> ('a, 'b) fg option, 'a, 'b) wrap
  val tail_exn : (('a, 'b) fg -> ('a, 'b) fg, 'a, 'b) wrap
  val init : (('a, 'b) fg -> ('a, 'b) fg option, 'a, 'b) wrap
  val init_exn : (('a, 'b) fg -> ('a, 'b) fg, 'a, 'b) wrap
  val rear : (('a, 'b) fg -> (('a, 'b) fg * 'a) option, 'a, 'b) wrap
  val rear_exn : (('a, 'b) fg -> ('a, 'b) fg * 'a, 'a, 'b) wrap
  val is_empty : ('a, 'b) fg -> bool
  val fold_left : ('-> '-> 'a) -> '-> ('b, 'c) fg -> 'a
  val fold_right : ('-> '-> 'a) -> '-> ('b, 'c) fg -> 'a
  val iter : ('-> unit) -> ('a, 'b) fg -> unit
  val iter_right : ('-> unit) -> ('a, 'b) fg -> unit
  val compare : ('-> '-> int) -> ('a, 'b) fg -> ('a, 'b) fg -> int
  val equal : ('-> '-> bool) -> ('a, 'b) fg -> ('a, 'b) fg -> bool
  val enum : ('a, 'b) fg -> 'BatEnum.t
  val backwards : ('a, 'b) fg -> 'BatEnum.t
  val to_list : ('a, 'b) fg -> 'a list
  val to_list_backwards : ('a, 'b) fg -> 'a list
  val of_enum : ('BatEnum.t -> ('a, 'b) fg, 'a, 'b) wrap
  val of_backwards : ('BatEnum.t -> ('a, 'b) fg, 'a, 'b) wrap
  val of_list : ('a list -> ('a, 'b) fg, 'a, 'b) wrap
  val of_list_backwards : ('a list -> ('a, 'b) fg, 'a, 'b) wrap
  val map : (('-> 'b) -> ('a, 'c) fg -> ('b, 'c) fg, 'b, 'c) wrap
  val map_right : (('-> 'b) -> ('a, 'c) fg -> ('b, 'c) fg, 'b, 'c) wrap
  val append : (('a, 'b) fg -> ('a, 'b) fg -> ('a, 'b) fg, 'a, 'b) wrap
  val reverse : (('a, 'b) fg -> ('a, 'b) fg, 'a, 'b) wrap
  val print :
    ?first:string ->
    ?last:string ->
    ?sep:string -> ('a, 'b) BatIO.printer -> (('a, 'c) fg, 'b) BatIO.printer
  val size : 'BatFingerTree.t -> int
  val split_at :
    'BatFingerTree.t -> int -> 'BatFingerTree.t * 'BatFingerTree.t
  val get : 'BatFingerTree.t -> int -> 'a
  val set : 'BatFingerTree.t -> int -> '-> 'BatFingerTree.t
  val update : 'BatFingerTree.t -> int -> ('-> 'a) -> 'BatFingerTree.t
  val of_list_for_test : 'a list -> 'BatFingerTree.t
  val verify_measure : 'BatFingerTree.t -> 'BatFingerTree.t
  val invariants : 'BatFingerTree.t -> unit
end