CODEWITHSUNDEEP
ocamlsmlml
xiang
xiang

Reputation: 1534

How to achieve the type-class of sml？

I want to write a comparable set as below.

signature COMPARABLE_SET=
sig
  type 'a set
  val empty: 'a set
  val insert: 'a * 'a set -> 'a set
  val member: 'a * 'a set -> bool
end

I need to limit the element in 'a set type to be comparable：(there is a function with type:'a * 'a -> order).

How to achieve it?

Upvotes: 2

Views: 456

Answers (1)

Lhooq
Lhooq

Reputation: 4441

If you want to do it in OCaml, this is simply a functor case :

First, you need to define the type of your elements :

module type OrderedType = sig 
  type t 
  val compare : t -> t -> int
end

And then you'll define a functor on this type :

module MakeComparableSet (Ord : OrderedType) :
  sig
    type elt = Ord.t
    type t
    val empty : t
    val insert : elt -> t -> t
    val member : elt -> t -> bool
  end = struct
    type elt = Ord.t
    type t
    let empty = failwith "TODO"
    let insert = failwith "TODO"
    let member = failwith "TODO"
  end

Which is exactly what is made here.

You can see a functor as a function on module that will create new modules. Here, the functor ComparableSet takes a module of signature OrderedType and returns a module that is a set.

Upvotes: 4

Related Questions