Question on Variant Types
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:   (:) 
From:  Jonathan Roewen <jonathan.roewen@g...> 
Subject:  Re: [Camllist] Question on Variant Types 
On 6/29/06, Seth J. Fogarty <sfogarty@gmail.com> wrote: > 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 ;) Jonathan