Re: [Caml-list] Question on Variant Types

["Jonathan Roewen" <jonathan.roewen@gmail.com>]

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