[Caml-list] polymorphic variant typing question

[skaller <skaller@users.sourceforge.net>]

Consider this:

type ('x, 'a) regexp_t' =
  [
  | `REGEXP_char of int
  | `REGEXP_seq of 'x * 'x (** concatenation *)
  | `REGEXP_alt of 'x * 'x (** alternation *)
  | `REGEXP_aster of 'x (** Kleene closure *)
  | `REGEXP_epsilon (** epsilon: null string *)
  | `REGEXP_code of 'a (** associated code *)
  ] 

type 'a regexp_t = ('x, 'a) regexp_t' as 'x


(* extend the regexp type -- polymorpic variants are wonderful! *)
type 'a gre_t = [ 
  | ('b,'a) regexp_t' 
  | `REGEXP_group of 'b
  ] as 'b
;;

type 'b gcode = [`User of 'b | `Left of int | `Right of int ]
;;

let groupify (re: 'a gre_t) : 'a gcode regexp_t =
  let counter = ref 0 in
  let rec aux (re: 'a gre_t) : 'a gcode regexp_t = match re with
  | `REGEXP_group a ->
    let n = !counter in incr counter;
    let a = aux a in
    seq (seq (code (`Left n)) a) (code (`Right n))
    
  | `REGEXP_code a -> `REGEXP_code (`User a)
  | `REGEXP_alt (a,b) -> 
    let a = aux a in
    let b = aux b in
    `REGEXP_alt (a,b)

  | `REGEXP_seq (a,b) -> 
    let a = aux a in
    let b = aux b in
    `REGEXP_alt (a,b)
  
  | `REGEXP_aster a -> `REGEXP_aster (aux a)
  | `REGEXP_epsilon -> `REGEXP_epsilon
  | `REGEXP_char c -> `REGEXP_char c
  in 
    aux re

What this does is extend the regular expression
type to allow a group combinator, but then reduce it
by using left/right bracket codes. This typing
compiles.

Question: how can I replace the last two lines of
the match with something which just handles 'all the
rest of the cases'?

Those cases are invariant, but a coercion

  | (x : 'a gre_t ) -> ( x : 'a gre_t :> 'a gcode regexp_t)

doesn't work because in general, 'a gre_t isn't a subtype
of 'a gcode regexp_t. I need to reduce the type functor
from gre_t to regexp_t, and 'a to 'a gcode.

Do I have to factor the original regexp_t into invariant
and variant parts??

[BTW: the typing of all this is awesome!]

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners