functor (Letter : Set.OrderedType) ->
  sig
    type position = int
    module Position : sig type t = position val compare : t -> t -> int end
    module PositionSet :
      sig
        type elt = position
        type t
        val empty : t
        val is_empty : t -> bool
        val mem : elt -> t -> bool
        val add : elt -> t -> t
        val singleton : elt -> t
        val remove : elt -> t -> t
        val union : t -> t -> t
        val inter : t -> t -> t
        val diff : t -> t -> t
        val compare : t -> t -> int
        val equal : t -> t -> bool
        val subset : t -> t -> bool
        val iter : (elt -> unit) -> t -> unit
        val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a
        val for_all : (elt -> bool) -> t -> bool
        val exists : (elt -> bool) -> t -> bool
        val filter : (elt -> bool) -> t -> t
        val partition : (elt -> bool) -> t -> t * t
        val cardinal : t -> int
        val elements : t -> elt list
        val min_elt : t -> elt
        val max_elt : t -> elt
        val choose : t -> elt
        val split : elt -> t -> t * bool * t
        val find : elt -> t -> elt
        val of_list : elt list -> t
      end
    type letter = Letter.t
    type regexp =
        RSym of (letter * position)
      | RSeq of (regexp * regexp)
      | REmpty
      | RChoice of (regexp * regexp)
      | RNone
      | RPlus of regexp
      | RStar of regexp
      | RAmp of (regexp * regexp)
    val nullable : regexp -> bool
    val pos : regexp -> PositionSet.t
    val first : regexp -> PositionSet.t
    val last : regexp -> PositionSet.t
    val follow : regexp -> position -> PositionSet.t
    val chi : regexp -> position -> letter
    val star_normalize_aux : regexp -> regexp
    val star_normalize : regexp -> regexp
  end