[Caml-list] "subclassing" a char map

[Caml-list] "subclassing" a char map

[Martin DeMello]

I have a char multiset defined via

module MultiSet = Map.Make(struct type t = char let compare = compare end)

Now I would like to split off a distinct type that can only contain
A-Z as keys. What's the best way to do this?

martin

Re: [Caml-list] "subclassing" a char map

[Ivan Gotovchits]

Martin DeMello <martindemello@gmail.com> writes:

> I have a char multiset defined via
>
> module MultiSet = Map.Make(struct type t = char let compare = compare end)
>
> Now I would like to split off a distinct type that can only contain
> A-Z as keys. What's the best way to do this?
>
> martin

Not sure, that I correctly understood your needs... but you can
implement «A-Z keys» as an abstract type, contained in a module with the
following signature:

module type Caps =  sig
  type t
  val create: char -> t option
  val compare: t -> t -> int
  val project: t -> char
end

Next, you can instatiate a Map from abstract type Cap.t to 'a:

module CapMap = Map.Make(Caps)

where Caps is an implementation, conforming to the signature Caps. For
example like this:

module Caps : Caps = struct
    type t = char
    let create = function
      | 'A'..'Z' as ch -> Some ch
      | otherwise      -> None
    let compare = compare
    let project ch = ch
end

-- 
         (__) 
         (oo) 
   /------\/ 
  / |    ||   
 *  /\---/\ 
    ~~   ~~   
...."Have you mooed today?"...

Re: [Caml-list] "subclassing" a char map

[Martin DeMello]

Ah, thanks, that will do very nicely. I just wanted a type of char map
I couldn't insert anything else other than A-Z into, that the
typechecker would prevent me from mixing with the regular char map.

martin

On Sun, Sep 15, 2013 at 9:20 PM, Ivan Gotovchits <ivg@ieee.org> wrote:
> Martin DeMello <martindemello@gmail.com> writes:
>
>> I have a char multiset defined via
>>
>> module MultiSet = Map.Make(struct type t = char let compare = compare end)
>>
>> Now I would like to split off a distinct type that can only contain
>> A-Z as keys. What's the best way to do this?
>>
>> martin
>
> Not sure, that I correctly understood your needs... but you can
> implement «A-Z keys» as an abstract type, contained in a module with the
> following signature:
>
> module type Caps =  sig
>   type t
>   val create: char -> t option
>   val compare: t -> t -> int
>   val project: t -> char
> end
>
> Next, you can instatiate a Map from abstract type Cap.t to 'a:
>
> module CapMap = Map.Make(Caps)
>
> where Caps is an implementation, conforming to the signature Caps. For
> example like this:
>
> module Caps : Caps = struct
>     type t = char
>     let create = function
>       | 'A'..'Z' as ch -> Some ch
>       | otherwise      -> None
>     let compare = compare
>     let project ch = ch
> end
>
> --
>          (__)
>          (oo)
>    /------\/
>   / |    ||
>  *  /\---/\
>     ~~   ~~
> ...."Have you mooed today?"...

Re: [Caml-list] "subclassing" a char map

[Goswin von Brederlow]

On Sun, Sep 15, 2013 at 09:31:34PM -0700, Martin DeMello wrote:
> Ah, thanks, that will do very nicely. I just wanted a type of char map
> I couldn't insert anything else other than A-Z into, that the
> typechecker would prevent me from mixing with the regular char map.
> 
> martin
> 
> On Sun, Sep 15, 2013 at 9:20 PM, Ivan Gotovchits <ivg@ieee.org> wrote:
> > Martin DeMello <martindemello@gmail.com> writes:
> >
> >> I have a char multiset defined via
> >>
> >> module MultiSet = Map.Make(struct type t = char let compare = compare end)
> >>
> >> Now I would like to split off a distinct type that can only contain
> >> A-Z as keys. What's the best way to do this?
> >>
> >> martin
> >
> > Not sure, that I correctly understood your needs... but you can
> > implement «A-Z keys» as an abstract type, contained in a module with the
> > following signature:
> >
> > module type Caps =  sig
> >   type t
> >   val create: char -> t option
> >   val compare: t -> t -> int
> >   val project: t -> char
> > end
> >
> > Next, you can instatiate a Map from abstract type Cap.t to 'a:
> >
> > module CapMap = Map.Make(Caps)
> >
> > where Caps is an implementation, conforming to the signature Caps. For
> > example like this:
> >
> > module Caps : Caps = struct
> >     type t = char
> >     let create = function
> >       | 'A'..'Z' as ch -> Some ch
> >       | otherwise      -> None
> >     let compare = compare
> >     let project ch = ch
> > end

I recommend using a private type (in the module type) over an abstract
one:
    type t = private char

That way a type t instance can only be constructed in the module,
where you check the upper case, but can be used in place of a char
otherwise. No need to manually project it everywhere.

MfG
	Goswin

Re: [Caml-list] "subclassing" a char map

[Martin DeMello]

On Mon, Sep 16, 2013 at 12:42 AM, Goswin von Brederlow
<goswin-v-b@web.de> wrote:
>
> I recommend using a private type (in the module type) over an abstract
> one:
>     type t = private char
>
> That way a type t instance can only be constructed in the module,
> where you check the upper case, but can be used in place of a char
> otherwise. No need to manually project it everywhere.

Thanks, didn't know about that feature at all. After a bit of googling
I found https://ocaml.janestreet.com/?q=node/77, which is a nice write
up on the subject.

martin

Re: [Caml-list] "subclassing" a char map

[oleg]

> I just wanted a type of char map I couldn't insert anything else other
> than A-Z into, that the typechecker would prevent me from mixing with
> the regular char map.

Using the abstract type and restricting its constructors -- that is,
controlling the ways the values of that type can be created -- lets us
statically ensure quite strong invariants. For example, subranging (as
in your A-Z example) or primality of integers, etc. The best part:
this type safety can be achieved without any dependent or other fancy
types, using any type system that supports abstract types.

That deep insight is from the 70s, and explained with great clarity in the
paper
        Protection in Programming Languages
        James H. Morris Jr.
        http://www.erights.org/history/morris73.pdf

His running example was also interval type. Incidentally, James
H. Morris has discovered quite a few other things we now take for
granted, for example, lazy evaluation
        http://www.cs.cmu.edu/~jhm/short%20biography.htm

The same insight -- the use of an abstract data type whose values can only
be produced by a trusted kernel, and the use of a type system to guarantee this
last property -- underlies Robin Milner's Edinburgh LCF theorem prover,
written at about the same time in early 1970s. ML was designed as a
scripting language of that prover.