Functions over polymorphic variants

Functions over polymorphic variants

[Kaspar Rohrer]

I am tinkering with streams of polymorphic variants at the moment. One thing that I would like to do is to write a stream transformer (not sure this is the correct terminology) that simply drops certain values of an open polymorphic type, and have the type of the function reflect this.

This is trivial with a closed polymorphic type:

type abc = [`a | `b | `c]

let transform (stream : [< `x | abc] Stream.t) : [> abc] Stream.t =
 let rec fold () =
     match Stream.next stream with
	| `x -> Stream.slazy fold
	| #abc as x -> Stream.icons x (Stream.slazy fold)
   with
	Stream.Failure -> Stream.sempty
 in
   fold ()

However, I fail to see how the same function could be implemented so it accepts an open polymorphic type as it's input.
I.e. is there a way to express something like this (which is not valid OCaml)

let transform : [> `x | 'a] Stream.t -> [> 'a] Stream.t

Does this even make sense?

----
Kaspar Rohrer
kaspar.rohrer@bluewin.ch

Re: [Caml-list] Functions over polymorphic variants

[Jacques Garrigue]

From: Kaspar Rohrer <kaspar.rohrer@gmail.com>
> I am tinkering with streams of polymorphic variants at the
> moment. One thing that I would like to do is to write a stream
> transformer (not sure this is the correct terminology) that simply
> drops certain values of an open polymorphic type, and have the type
> of the function reflect this.

Sorry, you can't.
This is a design choice with ocaml polymorphic variants, that the row
variable is kept hidden. This has the advantage of simplicity, but it
makes impossible to abstract on the row variable itself, like you want
here.

> This is trivial with a closed polymorphic type:
> 
> type abc = [`a | `b | `c]
> 
> let transform (stream : [< `x | abc] Stream.t) : [> abc] Stream.t =
>  let rec fold () =
>      match Stream.next stream with
> 	| `x -> Stream.slazy fold
> 	| #abc as x -> Stream.icons x (Stream.slazy fold)
>    with
> 	Stream.Failure -> Stream.sempty
>  in
>    fold ()
> 
> However, I fail to see how the same function could be implemented so it accepts an open polymorphic type as it's input.
> I.e. is there a way to express something like this (which is not valid OCaml)
> 
> let transform : [> `x | 'a] Stream.t -> [> 'a] Stream.t
> 
> Does this even make sense?

This makes sense, but would require a different type system.
With ocaml, you must keep to closed types.
This should be sufficient for concrete examples, but you cannot build
polymorphic combinators.

Note. In designing a type system where you would be able to express
such "differential" types, poinder the problem: what is the type of
transform composed with itself.

Jacques Garrigue

Re: [Caml-list] Functions over polymorphic variants

[Kaspar Rohrer]

Thank you for your concise answer. Am I correct when I say you are the author of the polymorphic variants and labels extension to OCaml?
As I stated earlier, I'm working somewhat heavily with PVs at the moment. One thing that bothers me is the error message for PV type mismatches.
As the PV types contain more than just a few tags, it becomes harder to identify the missing/different tags.

To come to the point: How hard would it be to patch the OCaml sources so that PV type mismatches would identify the offending tags?

To illustrate:

       Type declarations do not match:
         type input =
             [ `break
             | `fragment of string
             | `linebreak
             | `newline
             | `nop
             | `set_background of color
             | `set_context of context
             | `set_foreground of color
             | `set_intensity of intensity
             | `set_inverted of bool
             | `set_justification of justification
             | `set_underline of underline
             | `set_width of int
             | `space of int ]
       is not included in
         type input =
             [ `break
             | `fragment of string
             | `linebreak
             | `newline
             | `nop
             | `set_background of color
             | `set_context of context
             | `set_foreground of color
             | `set_intensity of intensity
             | `set_inverted of bool
             | `set_underline of underline
             | `space of int ]

Maybe the common tags could be omitted in a final digest:

       Type mismatch:
         type input =
             [ ...
             | `set_justification of justification
             | `set_width of int ]
       is not included in
         type input =
             [ ... ]

I guess open and closed PV types would complicate things a bit, but this should be possible, right?

Thank you

----
Kaspar Rohrer
kaspar.rohrer@gmail.com

On Mar 23, 2010, at 7:11 AM, Jacques Garrigue wrote:

> From: Kaspar Rohrer <kaspar.rohrer@gmail.com>
>> I am tinkering with streams of polymorphic variants at the
>> moment. One thing that I would like to do is to write a stream
>> transformer (not sure this is the correct terminology) that simply
>> drops certain values of an open polymorphic type, and have the type
>> of the function reflect this.
> 
> Sorry, you can't.
> This is a design choice with ocaml polymorphic variants, that the row
> variable is kept hidden. This has the advantage of simplicity, but it
> makes impossible to abstract on the row variable itself, like you want
> here.
> 
>> This is trivial with a closed polymorphic type:
>> 
>> type abc = [`a | `b | `c]
>> 
>> let transform (stream : [< `x | abc] Stream.t) : [> abc] Stream.t =
>> let rec fold () =
>>     match Stream.next stream with
>> 	| `x -> Stream.slazy fold
>> 	| #abc as x -> Stream.icons x (Stream.slazy fold)
>>   with
>> 	Stream.Failure -> Stream.sempty
>> in
>>   fold ()
>> 
>> However, I fail to see how the same function could be implemented so it accepts an open polymorphic type as it's input.
>> I.e. is there a way to express something like this (which is not valid OCaml)
>> 
>> let transform : [> `x | 'a] Stream.t -> [> 'a] Stream.t
>> 
>> Does this even make sense?
> 
> This makes sense, but would require a different type system.
> With ocaml, you must keep to closed types.
> This should be sufficient for concrete examples, but you cannot build
> polymorphic combinators.
> 
> Note. In designing a type system where you would be able to express
> such "differential" types, poinder the problem: what is the type of
> transform composed with itself.
> 
> Jacques Garrigue