neel-krishnaswami

module C : sig
  type t 
  val empty : t 
  val one : char -> t 
  val union : t -> t -> t 
  val inter : t -> t -> t 
  val top : t 
  val mem : char -> t -> bool 
  val make : (char -> bool) -> t 
  val equal : t -> t -> bool

neel-krishnaswami

type sort = Bool | Int | Array of sort 

type op = Plus | Times | Minus 

type var = string

type 'a termF = 
  | Var of var
  | Lit of int
  | Op of op * 'a * 'a 

neel-krishnaswami

module type KLEENE = sig
  type t 
  val zero : t 
  val one : t
  val ( * ) : t -> t -> t 
  val ( ++ ) : t -> t -> t 
  val star : t -> t 
end

module type MATRIX = sig

neel-krishnaswami

(* Types *)
module C = Set.Make(Char)
type tp = { null : bool; first : C.t; follow : C.t }

(* Grammars *)            
type t = 
  | Var of string
  | Fix of string * tp * t
  | Eps
  | Char of char

neel-krishnaswami

(* -*- mode: ocaml; -*- *)

module type NEXT =
sig
  type 'a t
  exception Timing_error of int * int 

  val delay  : (unit -> 'a) -> 'a t
  val map    : ('a -> 'b) -> 'a t -> 'b t
  val zip    : 'a t * 'b t -> ('a * 'b) t

neel-krishnaswami

module type CELL = sig
  type 'a cell
  type 'a exp

  val return : 'a -> 'a exp
  val (>>=) : 'a exp -> ('a -> 'b exp) -> 'b exp

  val cell : 'a exp -> 'a cell exp 
  val get :  'a cell -> 'a exp

neel-krishnaswami

(* -*- mode: ocaml; -*- *)

module type FUNCTOR = sig
  type 'a t
  val map : ('a -> 'b) -> 'a t -> 'b t
end

type 'a monoid = {unit : 'a ; join : 'a -> 'a -> 'a}

type var = string

neel-krishnaswami

type re = C of char | Nil | Seq of re * re | Bot | Alt of re * re | Star of re

let rec null = function
  | C _ | Bot -> false
  | Nil | Star _ -> true
  | Alt(r1, r2) -> null r1 || null r2
  | Seq(r1, r2) -> null r1 && null r2

module R = Set.Make(struct type t = re let compare = compare end)
let rmap f rs = R.fold (fun r -> R.add (f r)) rs R.empty