Containers interface & Passing constraints through functors

I am working on an exercise, whence I am trying to define some basic algorithms on arrays. Since arrays naturally includes string interfaces, I would like to also make sure that the infrastructure includes the possibility of using strings as input. I noticed that the way the strings are defined in the standard library (whether Stdlib or Base) is along the following lines:

module type STRING = sig
  type t
  type item
  val get : t -> int -> item

module String : STRING

whereas the definition for arrays is

module type ARRAY = sig
  type 'a t
  val get : 'a t -> int -> 'a

module Array : ARRAY

While trying to reconcile the differences in the type t arity in my interfaces, I have attempted the following approach to represent strings with an array

module Array_constrained
  (Itm : ITEM) =
  module type S = sig
    type 'a t constraint 'a = Itm.t
    val get : 'a t -> int -> 'a

Then I hoped to be able to use implement an interface that implements operations common to strings and arrays by doing the following:

module Common_ops
  (A : ARRAY) :
  val opus : 'a A.t -> int -> unit
end =
  (* implementation *)

and then use the result in the module implementing string operations as follows

module String_ops
  (Itm : ITEM)
  (Str : STRING) =
  module Immutable_array : 
    Array_constrained(Itm).S  =
    type 'a t = Str.t
    let get = Str.get
  include Common_ops(Immutable_array)

However, the functors that take type ARRAY do not take the type Array_constrained(Itm). Logically, it seems that setting variance on 'a t should have worked, since a constrained 'a in 'a t means that 'a has a narrower domain, and hence so does 'a t, which is precisely the basic concept that the variance should be representing. Yet, it does not. I am still getting an error about mismatching constraints in signatures.

I expected that Common_ops would be yielding an implementation with 'a in the type 'a A.t constrained in the same way as it has been in the input module A. Thus, passing a module matching Array_constrained(Itm).S to Common_ops should have yielded the interface of Common_ops with value opus taking values of type 'a A.t constraint 'a = Itm.t.

Could you please assist me with finding how to solve this problem, so that I would either be able to apply modules with constrained signature, or perhaps find some other approach to implementing interfaces that work both with STRING and ARRAY inputs, and in which common operations could be provided without code duplication. The solution whence e.g. two versions of Common_ops module provided, one for STRING and one for ARRAY is not acceptable.

Additional notes. Please note that it is undesirable to introduce interfaces whence the value of t would not be polymorphic, and the type of items stored in the container would be provided by a functor argument, even for arrays. In principle, such solution would be easy, and I have attempted it myself. However, I am at a loss, how to implement such solution so that it would result in a model signature with polymorphic 'a t. I am aware that it could be done with first-class modules and having a function produce output with polymorphic 'a t (while using the non-polymorphic 'a t to implement the modules it would be giving out as a result). However, I am not aware as to how I could make such a function to produce a static module of the required type. Is that even possible? Would the performance of the resulting modules be less efficient than in the case whence the first-class modules are not used? Please feel free to as for additional clarifications on these notes.

1 Like

I think the problem lies in that string type is not polymorphic and your required type is. Have you considered creating a polymorphic type from your string?

Welcome to the forums.

One of the resident experts should be able to help you out.

I’m not 100% sure I understand the problem you’re facing, but my inclination would be to reach for something akin to Base.Container_intf.Generic:

module type Generic = sig
  type 'a t
  type 'a elt

  val length : _ t -> int
  val is_empty : _ t -> bool
  val iter : 'a t -> f:('a elt -> unit) -> unit

You can then write the Common_ops functor to take a module with signature Generic:

module type Generic_container = sig
  type 'a t
  type 'a elt

  val get : 'a t -> int -> 'a elt

module Common_ops(C : Generic_container) = struct
  let get_first t = C.get t 0

  (* TODO More operations *)

module String_ops = Common_ops(struct
    type _ t = string
    type _ elt = char
    include (String : module type of String with type t := string)

module Array_ops = Common_ops(struct
    type 'a t = 'a array
    type 'a elt = 'a
    include Array

Thank you for your response. The issue is how could I possibly approach doing so? There are valid instances of string, like e.g. the one from the standard library, that are not polymorphic.

I could in principle do something like 'a t = String.t, but in that case I would certainly run into the same issue that I am having.

In my limited experience with OCaml(and programming in general), I would just hack around the problem. I would take the string and put it into a polymorphic type. Not elegant but it works.

module type ARRAY= 

  type 'a t

  val get : 'a t -> int -> 'a


module MyArray(E:ARRAY) =

  let get store place = E.get store place


module StrList =

  type 'a t = 'a list 

  let rec create str = 
    let len = String.length str in
    if len < 1
      (String.get str 0)::create (String.sub str 1 (len -1))

  let get store place = List.nth store place


module MyStrArr = MyArray(StrList)

let strArr = StrList.create "Hello There!"

let ans = MyStrArr.get strArr 6

let () = print_endline (String.make 1 ans)

The experts should be able to find a more elegant solution,

The problem here is precisely with the get operation. If we are limiting the type of what 'a could in fact be, then we will have to limit the type in the val get : 'a t -> int -> 'a, or else there would be a compile time error, with the return of get being too narrow (e.g. char could not be 'a).

I actually see now how this may work, since we are having 'a elt, but not 'a. Let me try to hack some sample code. Will attempt to report back, probably around tomorrow. Thank you for suggestion.


[some time later]

Trying out this approach brings up another question. Consider the case of definition

type 'a t
[@@deriving compare, sexp_of]

type 'a elt

The types of derived compare and sexp_of functions come out as

val compare : ('a -> 'a -> int) -> 'a t -> 'a t -> int

instead of

val compare : ('a elt -> 'a elt -> int) -> 'a t -> 'a t -> int

which is really the only possible type to actually define for custom definitions – and my implementation does require custom definitions. I think that generic comparisons of the form 'a -> 'a -> int for the case when e.g. 'a t = char is inappropriate anyway. However, I am concerned, how would definition like

('a elt -> 'a elt -> int) -> 'a t -> 'a t -> int


('a elt -> Sexp.t) -> 'a t -> Sexp.t

compose when [@@deriving compare] or [@@deriving sexp_of] is used with a structure that actually includes 'a t. Would the [@@deriving ...] annotations in those cases become useless anyway, and manual definition would be necessary? Should I define the compare as val compare : ('a elt -> 'a elt -> int) -> 'a t -> 'a t -> int manually and forgo the use of [@@deriving ...] functionality?

Yeah, the common case for parametric types anticipated by @@deriving compare, sexp_of does not apply here. You would have to define them manually (but it is not too bad, because the definitions are short and straightforward—basically the same thing that the deriving machinery would generate, but perhaps with some arguments missing, for example).

It seems that the approach with using 'a elt type works out quite well. In fact, I have chosen to supply the 'a elt type through a functor argument, a la

module Common_ops (Itm : sig type 'a t end) : sig
  type 'a t (* container type *)
  val opus : 'a t -> int -> int -> 'a Itm.t
end = struct
(* ... *)

I am still not feeling quite right about the signature

val compare : (char -> char -> int) -> 'a t -> 'a t -> int
val sexp_of_t : (char -> Sexp.t) -> 'a t -> Sexp.t

which are implemented as

let sexp_of_t _ data = String.sexp_of_t data
let compare _ data1 data2 = data1 data2

Since in that case I need to have the function accept the essentially dummy argument. At least, the [%sexp_of: 'a Common_ops.t] works satisfactorily.

I’d like to keep this topic open, until I finish the exercise, in case something pops up w.r.t. the interface definitions.

P.S. I am also wondering, how could I ask the original question about constraints in module types?

P.P.S. I have noticed that other posts have ocaml code color-coded. I didn’t find it in the FAQ how to accomplish that. Could someone please provide me with a suggestion about that?

If you begin your code block with:


it should be syntax highlighted.