This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

Question on Variant Types
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2006-06-29 (03:09) From: Jonathan Roewen Subject: Re: [Caml-list] 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

```