headers
skaller | 1 Sep 2006 01:29
Picon

Re: Re: Overriding an entry in a polymorphic variant

On Thu, 2006-08-31 at 18:04 -0400, Yaron Minsky wrote:
> On 8/31/06, Yaron Minsky <yminsky <at> cs.cornell.edu> wrote:
>         Does anyone know if there is a clean way of overriding a field
>         in a polymorhphic variant.  I want to do something like this:
>         
>         type bot = [ `bot ]
>         type top = [`bot | `top]
>         type t = [ `a of bot | `b of bot | `c of bot | `d of bot | `e
>         of bot ] 
>         type t1 = [ t | `c of top  | `e of top ]
>         
>         the desired end result being that t1 is actually [ `a of bot |
>         `b of bot | `c of top | `d of bot | `e of top ].  I'm hoping
>         to do this largely to enable some phantom-types hackery I'm
>         working on.  I'm not sure it matters from the point of view of
>         whether this is doable, but it is potentially relevant that
>         bot is a subtype of top.
> 
> Small addendum:  I'm still not sure this is relevant, 

It is ..

> but I did get my example slightly backwards.  top should be a subtype
> of bot, not the other way.  So the definitions of bot and top should
> be: 
> 
> type bot = [ `bot |  `top]
> type top = [`top]

Polymorphic variants are covariant in their arguments.
(Continue reading)

Permalink | Reply | 0 comments |
headers
Hendrik Tews | 1 Sep 2006 11:23
Picon
Favicon

Re: SafeUnmarshal: questions/problems/timings

Grégoire Henry <gregoire.henry <at> pps.jussieu.fr> writes:

   Hendrik wrote:

   > 1. I made some measurements that suggest that the
   >    unmarshal has quadratic complexity in the data size, see

   Therefore, if your data contains shared parts but no cycle, then it
   should be close to linear. Currently, mapping shared blocks to their
   type is represented by an association list: accessing such type
   information could explain this quadratic behaviour.

That would explain something: An association list hardly scales
to several megabyte of data.

   Could you please send us more information about the shape of your data
   (sharing or not, cycles or not, and wether sharing increase linearly
   or not with the size)?

The data contains sharing and cycles. I have no idea about the
height of the cycles. It might well be the case that the amount
of shared data grows faster than the overal size. But almost all
shared data has type string * int * int.

The data are abstract syntax trees of C++ programs (produced by a
modified elsa/elkhound parser). Its type is defined with about 40
recursive variant and record types. Its monomorphic, no aliasing
or other fancy features. I would say the type is bigger, but not
more complex than "int list". I would be really surprised if the
stronly connected components are necessary for my application.
(Continue reading)

Permalink | Reply | 0 comments |
headers
David MENTRE | 1 Sep 2006 19:06
Favicon

Re: Garbage collection and caml_adjust_gc_speed - Problem in Bigarray

Christopher Kauffman <kauffman <at> cs.umn.edu> writes:

> This now seems like an issue with the Bigarray library. Please advise me
> on the protocol for submitting this issue that it might be considered
> for correction in a future release.

Submit a bug report with as much details as possible on OCaml bug
tracker: http://caml.inria.fr/mantis/main_page.php

Best wishes,
d.
--

-- 
GPG/PGP key: A3AD7A2A David MENTRE <dmentre <at> linux-france.org>
 5996 CC46 4612 9CA4 3562  D7AC 6C67 9E96 A3AD 7A2A

_______________________________________________
Caml-list mailing list. Subscription management:
http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
Archives: http://caml.inria.fr
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs
Permalink | Reply | 0 comments |
headers
David Allsopp | 1 Sep 2006 19:31

Polymorphic variants question

Forgive the potentially obvious question --- I'm not very familiar with
polymorphic variants but I think that they're what I want in this situation!

Suppose I'm dealing with three constructors `A, `B and `C and I have a
function f that's supposed to take either `A or `C and return any of `A, `B
or `C. If I write:

let f x = if x = `A then (true, `B) else (false, x)

then I get the type

val f : ([> `A | `B] as 'a) -> bool * 'a

Now, if I try to constrain it to what I'm after with

let (f : [`A | `C] -> bool * [`A | `B | `C]) = fun x -> ...

then I get a type error unless I change
	(false, x)
to
	(false, id x)
with 
	let id = function `A -> `A | `C -> `C

Is there a better way of writing this? I'm using this in the context of
several interrelated lexers where `A, `B and `C are high-level states and
certain lexers can only be called in a subset of those states but each lexer
may yield any value for the next-state. I'd quite like to eliminate the id x
bit since it's only there to "separate" x from the return value for the
type-checker.
(Continue reading)

Permalink | Reply | 15 comments |
headers
Chris King | 1 Sep 2006 20:33
Picon

Re: Polymorphic variants question

On 9/1/06, David Allsopp <dra-news <at> metastack.com> wrote:
> Now, if I try to constrain it to what I'm after with
> 
> let (f : [`A | `C] -> bool * [`A | `B | `C]) = fun x -> ...
> 
> then I get a type error unless I change
> 	(false, x)
> to
> 	(false, id x)
> with 
> 	let id = function `A -> `A | `C -> `C
> 
> Is there a better way of writing this?

Yes, you can use the coercion operator to tell the compiler to expand the type of x to include `B:

# let f (x: [`A | `C]) = if x = `A then (true, `B) else (false, (x :> [`A | `B | `C]))
val f : [ `A | `C ] -> bool * [ `A | `B | `C ] = <fun>

Perhaps someone else can clarify how this accomplishes the same thing as your id function, as my
understanding of type theory is somewhat rudimentary.

- Chris King

_______________________________________________
Caml-list mailing list. Subscription management:
http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
Archives: http://caml.inria.fr
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs
(Continue reading)

Permalink | Reply | 3 comments |
headers
Olivier Andrieu | 1 Sep 2006 20:40
Favicon

Re: Polymorphic variants question

 David Allsopp [Friday 1 September 2006] :
 >
 > Forgive the potentially obvious question --- I'm not very familiar with
 > polymorphic variants but I think that they're what I want in this situation!
 > 
 > Suppose I'm dealing with three constructors `A, `B and `C and I have a
 > function f that's supposed to take either `A or `C and return any of `A, `B
 > or `C. If I write:
 > 
 > let f x = if x = `A then (true, `B) else (false, x)
 > 
 > then I get the type
 > 
 > val f : ([> `A | `B] as 'a) -> bool * 'a
 > 
 > Now, if I try to constrain it to what I'm after with
 > 
 > let (f : [`A | `C] -> bool * [`A | `B | `C]) = fun x -> ...
 > 
 > then I get a type error unless I change
 > 	(false, x)
 > to
 > 	(false, id x)
 > with 
 > 	let id = function `A -> `A | `C -> `C
 > 
 > Is there a better way of writing this? I'm using this in the context of
 > several interrelated lexers where `A, `B and `C are high-level states and
 > certain lexers can only be called in a subset of those states but each lexer
 > may yield any value for the next-state. I'd quite like to eliminate the id x
(Continue reading)

Permalink | Reply | 0 comments |
headers
skaller | 1 Sep 2006 21:00
Picon

Re: Re: Polymorphic variants question

On Fri, 2006-09-01 at 14:33 -0400, Chris King wrote:
> On 9/1/06, David Allsopp <dra-news <at> metastack.com> wrote:
> > Now, if I try to constrain it to what I'm after with
> > 
> > let (f : [`A | `C] -> bool * [`A | `B | `C]) = fun x -> ...
> > 
> > then I get a type error unless I change
> > 	(false, x)
> > to
> > 	(false, id x)
> > with 
> > 	let id = function `A -> `A | `C -> `C
> > 
> > Is there a better way of writing this?
> 
> Yes, you can use the coercion operator to tell the compiler to expand the type of x to include `B:
> 
> # let f (x: [`A | `C]) = if x = `A then (true, `B) else (false, (x :> [`A | `B | `C]))
> val f : [ `A | `C ] -> bool * [ `A | `B | `C ] = <fun>
> 
> Perhaps someone else can clarify how this accomplishes the same thing as 
> your id function, as my understanding of type theory is somewhat rudimentary.

The problem is `C not `B. Looking at this expression:

if x = `A then (true, `B) else (false, x)

we know the result is a bool followed by:

  1. `B in the true case
(Continue reading)

Permalink | Reply | 2 comments |
headers
Jon Harrop | 1 Sep 2006 21:26
Favicon

Re: Polymorphic variants question

On Friday 01 September 2006 18:31, David Allsopp wrote:
> let f x = if x = `A then (true, `B) else (false, x);;

You probably want:

# let f = function `A -> true, `B | `C -> false, `C;;
val f : [< `A | `C ] -> bool * [> `B | `C ] = <fun>

> then I get a type error unless I change
> 	(false, x)
> to
> 	(false, id x)

Use coercion :> instead of an ad-hoc function:

# let (f : [`A | `C] -> bool * [`A | `B | `C]) =
    fun x -> if x = `A then (true, `B) else (false, (x :> [`A|`B|`C]));;
val f : [ `A | `C ] -> bool * [ `A | `B | `C ] = <fun>

> Is there a better way of writing this? I'm using this in the context of
> several interrelated lexers where `A, `B and `C are high-level states and
> certain lexers can only be called in a subset of those states but each
> lexer may yield any value for the next-state. I'd quite like to eliminate
> the id x bit since it's only there to "separate" x from the return value
> for the type-checker.

Note that the type of your id function is not 'a -> 'a:

# let id = function `A -> `A | `C -> `C;;
val id : [< `A | `C ] -> [> `A | `C ] = <fun>
(Continue reading)

Permalink | Reply | 0 comments |
headers
skaller | 1 Sep 2006 21:29
Picon

Re: Polymorphic variants question

On Fri, 2006-09-01 at 18:31 +0100, David Allsopp wrote:

> let f x = if x = `A then (true, `B) else (false, x)

> let (f : [`A | `C] -> bool * [`A | `B | `C]) = fun x -> ...

BTW: when using polymorphic variants I find it is a good idea to:

(a) provide names (aliases, abbreviations) for your types.

(b) annotate function arguments and returns -- if not
   all of them, focus on the top level ones: it's necessary
   for the mli file anyhow.

(c) Prefer

let f x = match x with | ...

over

let f = fun x -> ...

and

let f = function | ..

and in particular for big top level functions like

let f (x:t1):t2 = 
  print_endline ("In Debug " ^ string_of_t1 x);
(Continue reading)

Permalink | Reply | 8 comments |
headers
David Allsopp | 1 Sep 2006 21:57

RE: Re: Polymorphic variants question

-----Original Message-----
From: skaller [mailto:skaller <at> users.sourceforge.net] 
Sent: 01 September 2006 20:00

> On Fri, 2006-09-01 at 14:33 -0400, Chris King wrote:
> > On 9/1/06, David Allsopp <dra-news <at> metastack.com> wrote:

<snip>

> By using:
>
>   let id = function `A -> `A | `C -> `C
>
> the compiler knows (id x) can include `A 
> and it can include `C, the case
>
>   (true, `B)
>
> being returned says the return type can also be `B.
> So the return type can be bool followed by `A, `B,  or `C.
>
> Hope that makes sense :)

Which is my understanding too - the type of id is [< `A | `C] -> [> `A | `C]
which allows x to be "used" in a [> `A | `B | `C] context without actually
changing the type of x while type inference is going on. Which, I guess I
should've spotted, means I can write:

let f (x : [`A | `C]) : bool * [`A | `B | `C] =
    if x = `A
(Continue reading)

Permalink | Reply | 1 comment |

Gmane