> type foo = [`Nil | `Tree of foo] > type bar = [`Nil | `Leaf of int | `Tree of bar]
> let f x : foo = x > let g x : bar = x > let a = `Tree (`Nil) > let b = `Tree (a) > let c = `Tree (f a) > let d = `Tree (`Leaf 1)
> As is proper, I can run f on a, b, and c, but not on d. D is not a valid > foo. > But I cannot run g on c. This makes sense, as I have said 'a tree of bars > contains a bars.' But I want to somehow note that a tree of bars MIGHT > contain foo's. Is there any way to annotate this? >From the ocaml reference docs:
# let bar_of_foo t = (t : foo :> bar);; val bar_of_foo : foo -> bar = <fun> # g (bar_of_foo c);; - : bar = `Tree (`Tree `Nil)
> If you have time, I have one more question I can't seem to solve. Which > quite possibly has as simple an answer as the other two. You've been very > helpful so far, and I don't want to impose, so feel free to let me know if > you've not the time.
> type foo = [`A of int | `B | 'D of foo] > type bar = [`A of int | `C of foo * bar | 'D of bar]
> let rec occurs i x = > match x with > |`A j -> i = j > |`C (foo, bar) -> (occurs i foo) or (occurs i bar) > |_ -> false
> I would like occurs to work on bars and foos. But as it is, occurs won't > work on either, because it assigns the `C variant the type "`C of 'b * 'b". > Even if I spell out `D and `B, I cannot get it to accept. Nor does:
> let rec occurs i (x : 'a) = > match x with > |`A j -> i = j > |`C ((foo : foo), (bar : bar)) -> > (occurs i (foo : foo :> 'a) or > (occurs i (bar : bar :> 'a))) > |_ -> false
> even compile.
> let rec occurs i x = > match x with > |`A j -> i = j > |(`C (foo, bar) : bar) -> (occurs i foo) or (occurs i bar) > |_ -> false
> has similar problems.
> Again, any assistance would be greatly appreciated, but is not necessary.
Only thing I could think of was:
# let rec occurs i = function | `A j -> i = j | `C (f,b) -> (occurs_foo i f) || (occurs_bar i b) | otherwise -> false and occurs_foo i = function | `A j -> i = j | otherwise -> false and occurs_bar i = function | `A j -> i = j | `C (f,b) -> (occurs_foo i f) || (occurs_bar i b) | otherwise -> false;; val occurs : 'a -> [> `A of 'a | `C of ([> `A of 'a ] as 'b) * ([> `A of 'a | `C of 'b * 'c ] as 'c) ] -> bool = <fun> val occurs_foo : 'a -> [> `A of 'a ] -> bool = <fun> val occurs_bar : 'a -> ([> `A of 'a | `C of [> `A of 'a ] * 'b ] as 'b) -> bool = <fun> # occurs 2 (`C ((`D (`B)), (`C (`A 3, (`D (`C (`A 4, `A 2)))))));; - : bool = false
Basically specialising on the two types. There may be a way to coerce them to not need it, but I'm not sure what it is.
Here are two other solutions:
# let rec occurs i x = let map = function | `A j -> `A j | `C (f,b) -> print_endline "C"; `C (f,b) | x -> `None in match map x with | `A j -> i = j | `None -> false | `C (f,b) -> (occurs i f) or (occurs i b);; val occurs : 'a -> ([> `A of 'a | `C of 'b * 'b ] as 'b) -> bool = <fun>
--
# let occurs i x = let map = function | `A _ | `C (_,_) as x -> x | _ -> `None in let rec occurs = function | `A j -> i = j | `C (f,b) -> (occurs (map f)) or (occurs (map b)) | `None -> false in occurs x;; val occurs : 'a -> [ `A of 'a | `C of ([> `A of 'a | `C of 'b * ([> `A of 'a | `C of 'b * 'c ] as 'c) ] as 'b) *
'c | `None ] -> bool = <fun>
Pretty damn ugly! But it works... Perhaps someone more proficient with variant types on the list can come up with a more reasonable solution than my hack ;-)
> If you have time, I have one more question I can't seem to solve. Which > quite possibly has as simple an answer as the other two. You've been very > helpful so far, and I don't want to impose, so feel free to let me know if > you've not the time.
> type foo = [`A of int | `B | 'D of foo] > type bar = [`A of int | `C of foo * bar | 'D of bar]
> let rec occurs i x = > match x with > |`A j -> i = j > |`C (foo, bar) -> (occurs i foo) or (occurs i bar) > |_ -> false
> I would like occurs to work on bars and foos. But as it is, occurs won't > work on either, because it assigns the `C variant the type "`C of 'b * 'b". > Even if I spell out `D and `B, I cannot get it to accept.
As long as foo and bar are two subtypes of a common type, you can still solve the problem by defining that type and using subtyping:
type foobar = [`A of int | `B | `C of foobar * foobar | `D of foobar] let occurs_foo i x = occurs i (x : foo :> foobar) let occurs_bar i x = occurs i (x : bar :> foobar)
I have another question on variant types which seems to be related to this, but perhaps the opposite way round. How can I get the code below to work? (It's simplified greatly from a real problem I'm having).
Rich.
---------------------------------------------------------------------- type colour = [ `Red | `Green | `Blue ] type colour' = [ colour | `Default ] type instructions = Set_foreground of colour' | Set_background of colour'
let default_fg : colour = `Red let default_bg : colour = `Green
let process_instructions = List.fold_left ( fun (fg, bg) -> function | Set_foreground `Default -> let new_fg = default_fg in (new_fg, bg) | Set_foreground new_fg -> (new_fg, bg) | Set_background `Default -> let new_bg = default_bg in (fg, new_bg) | Set_background new_bg -> (fg, new_bg) )
let string_of_colour = function | `Red -> "red" | `Green -> "green" | `Blue -> "blue"
let () = let instrs = [ Set_foreground `Blue; Set_background `Red; Set_foreground `Default ] in let fg, bg = `Green, `Blue in let fg, bg = process_instructions (fg, bg) instrs in print_endline ("fg = " ^ string_of_colour fg); print_endline ("bg = " ^ string_of_colour bg) ----------------------------------------------------------------------
-- Richard Jones, CTO Merjis Ltd. Merjis - web marketing and technology - http://merjis.com Team Notepad - intranets and extranets for business - http://team-notepad.com
> I have another question on variant types which seems to be related to > this, but perhaps the opposite way round. How can I get the code > below to work? (It's simplified greatly from a real problem I'm > having).
> Rich.
> ---------------------------------------------------------------------- > type colour = [ `Red | `Green | `Blue ] > type colour' = [ colour | `Default ] > type instructions = Set_foreground of colour' | Set_background of colour'
> let default_fg : colour = `Red > let default_bg : colour = `Green
> let process_instructions = > List.fold_left ( > fun (fg, bg) -> > function > | Set_foreground `Default -> > let new_fg = default_fg in > (new_fg, bg) > | Set_foreground new_fg -> > (new_fg, bg) > | Set_background `Default -> > let new_bg = default_bg in > (fg, new_bg) > | Set_background new_bg -> > (fg, new_bg) > )
> let string_of_colour = function > | `Red -> "red" > | `Green -> "green" > | `Blue -> "blue"
> let () = > let instrs = > [ Set_foreground `Blue; Set_background `Red; Set_foreground `Default ] in > let fg, bg = `Green, `Blue in > let fg, bg = process_instructions (fg, bg) instrs in > print_endline ("fg = " ^ string_of_colour fg); > print_endline ("bg = " ^ string_of_colour bg) > ----------------------------------------------------------------------
> -- > Richard Jones, CTO Merjis Ltd. > Merjis - web marketing and technology - http://merjis.com > Team Notepad - intranets and extranets for business - http://team-notepad.com
On Fri, Jun 30, 2006 at 09:51:01AM +1200, Jonathan Roewen wrote: > | Set_foreground (#colour as new_fg) ->
Thanks - that's exactly the syntax I was looking for.
Rich.
-- Richard Jones, CTO Merjis Ltd. Merjis - web marketing and technology - http://merjis.com Team Notepad - intranets and extranets for business - http://team-notepad.com
And now I have my own question about variant types :-)
I seem to be running into the problem of not being able to coerce polymorphic abstract types that use variants.
Eg:
type 'a t;;
type x = [ `Foo ];; type y = [ `Bar | x ];;
let widen x = (x : x t :> y t);;
Gives: Type x t is not a subtype of type y t Type x = [ `Foo ] is not compatible with type y = [ `Bar | `Foo ] The first variant type does not allow tag(s) `Bar
Yet the above approach works fine for non-abstract types.
On 7/1/06, Jonathan Roewen <jonathan.roe...@gmail.com> wrote:
> type 'a t;;
> type x = [ `Foo ];; > type y = [ `Bar | x ];;
> let widen x = (x : x t :> y t);;
> Gives: > Type x t is not a subtype of type y t > Type x = [ `Foo ] is not compatible with type y = [ `Bar | `Foo ] > The first variant type does not allow tag(s) `Bar
> Yet the above approach works fine for non-abstract types.
You need to explicitly specify the variance of 'a t:
type +'a t;;
This tells the type system that t is covariant with respect to 'a: if x is a subtype of y, then x t is a subtype of y t. Not all compound types share this property (most notably, mutable structures are invariant and function arguments are contravariant) so O'Caml must assume all abstract types to be invariant unless it's told otherwise.
