# Containers interface & Passing constraints through functors

**URL:** <https://discuss.ocaml.org/t/containers-interface-passing-constraints-through-functors/4011>\
**Category:** Learning\
**Tags:** type-system, base, types, functor\
**Created:** [July 1, 2019, 11:55am UTC](https://discuss.ocaml.org/t/containers-interface-passing-constraints-through-functors/4011 "2019-07-01T11:55:11Z")\
**Posts on this page:** 10\
**Page:** 1

<div class="post-metadata">

**Author:** ![s.t.s](https://avatars.discourse-cdn.com/v4/letter/s/c77e96/32.png) [@s.t.s](https://discuss.ocaml.org/u/s.t.s)\
**Post date:** [July 1, 2019, 11:55am UTC](https://discuss.ocaml.org/t/containers-interface-passing-constraints-through-functors/4011/1 "2019-07-01T11:55:11Z")

</div>

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
end

module String : STRING

```

whereas the definition for arrays is

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

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) =
struct
  module type S = sig
    type 'a t constraint 'a = Itm.t
    val get : 'a t -> int -> 'a
  end
end    

```

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) :
sig
  val opus : 'a A.t -> int -> unit
end =
struct
  (* implementation *)
end

```

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

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

```

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.

---

<div class="post-metadata">

**Author:** ![G4143](https://avatars.discourse-cdn.com/v4/letter/g/a88e57/32.png) [@G4143](https://discuss.ocaml.org/u/G4143)\
**Post date:** [July 1, 2019, 4:18pm UTC](https://discuss.ocaml.org/t/containers-interface-passing-constraints-through-functors/4011/2 "2019-07-01T16:18:11Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![bcc32](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/bcc32/32/203_2.png) [@bcc32](https://discuss.ocaml.org/u/bcc32)\
**Post date:** [July 1, 2019, 4:53pm UTC](https://discuss.ocaml.org/t/containers-interface-passing-constraints-through-functors/4011/3 "2019-07-01T16:53:45Z")

</div>

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`:

```ocaml
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
...
end

```

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

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

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

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

  (* TODO More operations *)
end

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

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

```

---

<div class="post-metadata">

**Author:** ![s.t.s](https://avatars.discourse-cdn.com/v4/letter/s/c77e96/32.png) [@s.t.s](https://discuss.ocaml.org/u/s.t.s)\
**Post date:** [July 1, 2019, 4:58pm UTC](https://discuss.ocaml.org/t/containers-interface-passing-constraints-through-functors/4011/4 "2019-07-01T16:58:09Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![G4143](https://avatars.discourse-cdn.com/v4/letter/g/a88e57/32.png) [@G4143](https://discuss.ocaml.org/u/G4143)\
**Post date:** [July 1, 2019, 5:25pm UTC](https://discuss.ocaml.org/t/containers-interface-passing-constraints-through-functors/4011/5 "2019-07-01T17:25:18Z")

</div>

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.

```auto
module type ARRAY= 
sig

  type 'a t

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

end

module MyArray(E:ARRAY) =
struct

  let get store place = E.get store place

end

module StrList =
struct

  type 'a t = 'a list 

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

  let get store place = List.nth store place

end

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,

---

<div class="post-metadata">

**Author:** ![s.t.s](https://avatars.discourse-cdn.com/v4/letter/s/c77e96/32.png) [@s.t.s](https://discuss.ocaml.org/u/s.t.s)\
**Post date:** [July 1, 2019, 6:06pm UTC](https://discuss.ocaml.org/t/containers-interface-passing-constraints-through-functors/4011/6 "2019-07-01T18:06:32Z")

</div>

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`).

---

<div class="post-metadata">

**Author:** ![s.t.s](https://avatars.discourse-cdn.com/v4/letter/s/c77e96/32.png) [@s.t.s](https://discuss.ocaml.org/u/s.t.s)\
**Post date:** [July 1, 2019, 6:09pm UTC](https://discuss.ocaml.org/t/containers-interface-passing-constraints-through-functors/4011/7 "2019-07-01T18:09:14Z")

</div>

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.

@bcc32

_[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

```

and

```
('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?

---

<div class="post-metadata">

**Author:** ![bcc32](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/bcc32/32/203_2.png) [@bcc32](https://discuss.ocaml.org/u/bcc32)\
**Post date:** [July 2, 2019, 4:48am UTC](https://discuss.ocaml.org/t/containers-interface-passing-constraints-through-functors/4011/8 "2019-07-02T04:48:48Z")

</div>

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).

---

<div class="post-metadata">

**Author:** ![s.t.s](https://avatars.discourse-cdn.com/v4/letter/s/c77e96/32.png) [@s.t.s](https://discuss.ocaml.org/u/s.t.s)\
**Post date:** [July 3, 2019, 2:45pm UTC](https://discuss.ocaml.org/t/containers-interface-passing-constraints-through-functors/4011/9 "2019-07-03T14:45:38Z")

</div>

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
(* ... *)
end

```

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 = String.compare 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?

---

<div class="post-metadata">

**Author:** ![bcc32](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/bcc32/32/203_2.png) [@bcc32](https://discuss.ocaml.org/u/bcc32)\
**Post date:** [July 3, 2019, 2:54pm UTC](https://discuss.ocaml.org/t/containers-interface-passing-constraints-through-functors/4011/10 "2019-07-03T14:54:04Z")

</div>

> [@s.t.s](#):
>
> 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:

````auto
```ocaml

````

it should be syntax highlighted.