English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

Browse thread
[Caml-list] polymorphic variant typing question
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2004-09-11 (07:49)
From: skaller <skaller@u...>
Subject: [Caml-list] polymorphic variant typing question
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
    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

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