Recursive functor module type

Learning
,
1

Hello, I’m trying to write a side project heavily relying on functors and it turns out that I don’t know how to declare the module type of a functor.

Here’s my code :

module type Ring_spec = sig
  val modulo : Z.t
  val degree : int
end

module Z_s (S : Ring_spec) = struct
  include Z

  type t = Z.t

  let ( % ) a b =
    let res = a mod b in
    if res < zero then
      res + b
    else
      res

  let add a b = Z.add a b % S.modulo
  let sub a b = Z.sub a b % S.modulo
  let mul a b = Z.mul a b % S.modulo
end
module type E = sig
  type t

  val zero : t
  val ( <+> ) : t -> t -> t
  val ( <-> ) : t -> t -> t
  val ( <*> ) : t -> t -> t
end

module Vector (N : E) = struct
  type t = N.t array

  let make n = CCArray.make n N.zero
  let get t i = t.(i)
  let set t i x = t.(i) <- x
  let length t = CCArray.length t

  let add a b =
    let open N in
    let n = length a in
    let r = make n in
    for i = 0 to n - 1 do
      r.(i) <- a.(i) <+> b.(i)
    done;
    r
end

module Matrix (N : E) = struct
  type t = N.t array array

  type direction =
    | Lines
    | Columns

  let make m n = CCArray.make_matrix m n N.zero
  let get t i j = t.(i).(j)
  let set t i j x = t.(i).(j) <- x

  let length dir t =
    match dir with
    | Lines -> CCArray.length t
    | Columns -> CCArray.length t.(0)

  let mul a b =
    let open N in
    if length Columns a <> length Lines b then invalid_arg "Matrix.mul";
    let m = length Lines a in
    let n = length Columns b in
    let p = length Lines b in

    let r = make m n in
    for i = 0 to m - 1 do
      for j = 0 to m - 1 do
        for k = 0 to p - 1 do
          r.(i).(j) <- r.(i).(j) <+> (a.(i).(k) <*> b.(k).(j))
        done
      done
    done;
    r

  let mul_v a (v : Vector(N).t) =
    let open N in
    let module Vec = Vector (N) in
    let m = length Lines a in
    let n = Vec.length v in

    let r = Vec.make m in
    for i = 0 to m - 1 do
      for j = 0 to n - 1 do
        r.(i) <- r.(i) <+> (a.(i).(j) <*> Vec.get v j)
      done
    done;
    r
end

(* Polynomial *)
module type Polynomial_sig = sig
  type t

  val make : int -> t
  val ( <+> ) : t -> t -> t
  val ( <-> ) : t -> t -> t
  val ( <*> ) : t -> t -> t
end

module Polynomial (N : E) (S : Ring_spec) = struct
  type t = N.t array

  let zero = CCArray.make S.degree N.zero
  let ( <+> ) = CCArray.map2 N.( <+> )
  let ( <-> ) = CCArray.map2 N.( <-> )
  let ( <*> ) = CCArray.map2 N.( <*> )
end

module type Ring_sig = sig
  module Z_s : sig
    include module type of Z

    val ( % ) : Z.t -> Z.t -> Z.t
    val ( <+> ) : Z.t -> Z.t -> Z.t
    val ( <-> ) : Z.t -> Z.t -> Z.t
    val ( <*> ) : Z.t -> Z.t -> Z.t
  end

  module Polynomial : Polynomial_sig with type t = Z_s.t
  (* module Vector : Vector_signature some how ?? <--- here
     module Matrix : Matrix_signature some how ?? <--- here *)
end

module Ring (S : Ring_spec) : Ring_sig (* Here) *)  = struct
  module Z_s = struct
    include Z

    type t = Z.t

    let ( % ) a b =
      let res = a mod b in
      if res < Z.zero then
        res + b
      else
        res

    let ( <+> ) a b = Z.add a b % S.modulo
    let ( <-> ) a b = Z.sub a b % S.modulo
    let ( <*> ) a b = Z.mul a b % S.modulo
  end

  module Polynomial = Polynomial (Z_s) (S)
  module Vector = Vector (Polynomial)
  module Matrix = Matrix (Polynomial)
end

I’d like to finish module type declaration of Ring_sig with Matrix_sig and Vector_sig (see “Here” in the code) yet I don’t know at all how to proceed, as Matrix has functions with functorized Vector(N).t or just N.t in their signature.

I’m sure that there’s a trick, yet I’m unable to find it.

Also please correct me if I’m not using the correct terminology about functors, it’s not something that I use on a daily basis.

2

Usually, you would do something like this:

module type Vector_sig = sig
   type elt
   type t
   val make : int -> t
   val get : t -> int -> elt
   val set : t -> int -> elt -> unit
   ...
end

and then:

(* in your vector functor *)
module Vector (N : E) = struct
     type elt = N.t
     type  = elt array
  ...
end
...
(* in your Ring functor *)

  module Polynomial : Polynomial_sig with type t = Z_s.t
  module Vector : Vector_sig with type elt = Polynomial.t

I think this should work.

2 Likes