Type abstraction with functor alarms type error

Community
,
1

Hi, I’m newbie to type abstraction using OCaml module. I’ve just read “Functors” part in manual. I’m implementing AbstractSet that takes any type which has order, based on sorted list. (similar to the example of that documents)

However, when doing this together with separating compile unit, I stuck at some point. I think showing my code is more straightforward that summarizing it. (Since I’m not used to the terminologies related to this topic)

OrderedTypes.ml: (It’s almost same with the manual)

type comparison = Less | Equal | Greater

module type ORDERED_TYPE =
  sig
    type t
    val compare: t -> t -> comparison
  end

module OrderedString : ORDERED_TYPE =
  struct
    type t = string
    let compare x y =
      if x = y then Equal
      else if x < y then Less
      else Greater
  end;;

Set.ml: Set based on sorted list

module type SET =
  functor (Elt: ORDERED_TYPE) ->
    sig
      type element
      type set
      val empty : set
      val add : element -> set -> set
      val member : element -> set -> bool
    end

module AbstractSet_L =
  functor (Elt: ORDERED_TYPE) ->
    struct
      type element = Elt.t
      type set = element list
      let empty = []
      let rec add x s =
        match s with
          [] -> [x]
        | hd::tl ->
            match Elt.compare x hd with
              Equal -> s
            | Less -> x :: s
            | Greater -> hd :: add x tl
      let rec member x s =
        match s with
          [] -> false
        | hd::tl ->
            match Elt.compare x hd with
              Equal -> true
            | Less -> false
            | Greater -> member x tl
    end

main.ml: simple test code using my set

open OrderedTypes
open Set

module StringSet = AbstractSet_L(OrderedString);;

let string_set_ex = StringSet.empty in
let string_set_ex = StringSet.add "hi" string_set_ex in
Printf.printf "%B" StringSet.member "hi" string_set_ex;

When I compile these with following commands,

ocamlc -c OrderedTypes.ml
ocamlc -c Set.ml
ocamlc -c main.ml

the error occurs in main.ml at the point StringSet.add "hi" string_set_ex

8 | let string_set_ex = StringSet.add "hi" string_set_ex in
                                      ^^^^
Error: This expression has type string but an expression was expected of type
         OrderedTypes.OrderedString.t

I understood that this is because of type abstraction of the element of Set, which my functor SET produces. The mentioned manual also deals with this issue in 40p, but my situation is slightly different. The document is using restriction on pre-defined SET signature with with type element = Elt.t phrase. I don’t know how to apply this style to my code, with my SET functor producing the anonymous signature.

I’ve tried to add with type element = Elt.t to SET like follows, but the error on main.ml still remains

module type SET =
  functor (Elt: ORDERED_TYPE) ->
    (sig
      type element
      type set
      val empty : set
      val add : element -> set -> set
      val member : element -> set -> bool
    end with type element = Elt.t)
2

When you say module OrderedString : ORDERED_TYPE = ..., you aren’t just saying that OrderedString is compatible with the module type ORDERED_TYPE. You’re constraining it to have exactly that module type, including the fact that t is an abstract type. Therefore no code outside of the OrderedString module has access to the fact that OrderedString.t = string.

If you want to follow the with type t = string solution, you could add that to the line of code I quoted, i.e.

module OrderedString : ORDERED_TYPE with type t = string =

As an aside, it doesn’t look like your SET module type is actually used anywhere. If you wanted AbstractSet_L to be constrained to that functor type, you would have to say so explicitly, as with

module AbstractSet_L : SET = ...
1 Like
3

As has already explained by @Levi_Roth the problem is your declaration of module OrderedString: ORDERED_TYPE. Nobody outside your module knows that OrderedString.t is equivalent to string. The simplest solution: Declare

    module OrderedString = struct
         type t = string
         ...
    end

and leave out the module type ORDERED_TYPE. Then the module OrderedString still complies with the interface ORDERED_TYPE, but it is visible that t = string.

This has the same effect as the solution proposed by @Levi_Roth.

4

I understand your solution. Thanks for your answering. However, it still has a compile error with main.ml, slightly different from the previous one.

8 | let string_set_ex = StringSet.add "hi" string_set_ex in
                                      ^^^^
Error: This expression has type string but an expression was expected of type
         StringSet.element =
           Set.AbstractSet_L(OrderedTypes.OrderedString).element

I think the problem of abstracting t of ORDERED_TYPE is solved, but another problem of abstracting element of the signature produced by the functor SET.

After reading @hbr’s comment, I’m also considering of removing ORDERED_TYPE from my implementation. However, I figured out that it is non-sense since I’m implementing a functor to build set with any ordered type.

5

Both solutions work. I have tried the following which compiles perfectly.

    type comparison = Less | Equal | Greater

    module type ORDERED_TYPE =
      sig
        type t
        val compare: t -> t -> comparison
      end

    module OrderedString: ORDERED_TYPE with type t = string =
    (* or simply 'module OrderedString' *)
      struct
        type t = string
        let compare x y =
          if x = y then Equal
          else if x < y then Less
          else Greater
      end

    module type SET =
      functor (Elt: ORDERED_TYPE) ->
        (sig
          type element
          type set
          val empty : set
          val add : element -> set -> set
          val member : element -> set -> bool
        end with type element = Elt.t)


    module AbstractSet_L: SET =
      functor (Elt: ORDERED_TYPE) ->
        struct
          type element = Elt.t
          type set = element list
          let empty = []
          let rec add x s =
            match s with
              [] -> [x]
            | hd::tl ->
                match Elt.compare x hd with
                  Equal -> s
                | Less -> x :: s
                | Greater -> hd :: add x tl
          let rec member x s =
            match s with
              [] -> false
            | hd::tl ->
                match Elt.compare x hd with
                  Equal -> true
                | Less -> false
                | Greater -> member x tl
        end


    module StringSet = AbstractSet_L(OrderedString)

    let string_set_ex = StringSet.empty
    let string_set_ex = StringSet.add "hi" string_set_ex
1 Like
6

I’ve forgotten to add with type element = Elt.t to the signature produced by SET functor. Thank you very much. It works well! :slight_smile:

7

Remark: sig type element ... end with type element = Elt.t can be written more concisely: sig type element = Elt.t ... end.

1 Like
8

@thierry-martinez: This is exactly how I would have done it. But I wanted to stay as close as possible to the original question. But you are right. It makes no sense to declare an abstract type element in a signature and immediately modify the signature by with type element = ....

An abstract type in a signature only makes sense if the concretisation of the type is not known at the declaration point of the signature.

1 Like
9

I think this is much more concise considering the meaning of abstract type in a signature, mentioned by @hbr. Thank you all for kind answers