From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by yquem.inria.fr (Postfix) with ESMTP id 2873BBB84 for ; Thu, 29 Jun 2006 05:09:11 +0200 (CEST) Received: from nz-out-0102.google.com (nz-out-0102.google.com [64.233.162.206]) by nez-perce.inria.fr (8.13.6/8.13.6) with ESMTP id k5T39BMs016681 for ; Thu, 29 Jun 2006 05:09:11 +0200 Received: by nz-out-0102.google.com with SMTP id o1so12031nzf for ; Wed, 28 Jun 2006 20:09:10 -0700 (PDT) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references; b=PUaTYjGPTtldBHMlPZkHRP6Udx7RiXKPADQ0T1vXX8tRIUUklL1GBLuzHL5shWXueMfdKnmwC0+9t3p/9i4WH2xjsYcgotr3dWri9uKW4tql3GVM7BxyJljoG6WqiaXYoHiuaWK7sXGw9hfiQ0bG2NAGnAdYz5IRuHAqyiJltFk= Received: by 10.36.50.15 with SMTP id x15mr2225554nzx; Wed, 28 Jun 2006 20:09:09 -0700 (PDT) Received: by 10.36.101.10 with HTTP; Wed, 28 Jun 2006 20:09:09 -0700 (PDT) Message-ID: Date: Thu, 29 Jun 2006 15:09:09 +1200 From: "Jonathan Roewen" To: "Seth J. Fogarty" Subject: Re: [Caml-list] Question on Variant Types Cc: OCaml In-Reply-To: MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Content-Disposition: inline References: X-j-chkmail-Score: MSGID : 44A34457.000 on nez-perce : j-chkmail score : X : 0/20 1 X-Miltered: at nez-perce with ID 44A34457.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; foo:01 foo:01 rec:01 rec:01 val:01 bool:01 val:01 bool:01 endline:01 wrote:01 caml-list:01 compile:01 int:01 int:01 variant:02 X-Spam-Checker-Version: SpamAssassin 3.0.3 (2005-04-27) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.4 required=5.0 tests=DNS_FROM_RFC_ABUSE,RCVD_BY_IP autolearn=disabled version=3.0.3 On 6/29/06, Seth J. Fogarty 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 = val occurs_foo : 'a -> [> `A of 'a ] -> bool = val occurs_bar : 'a -> ([> `A of 'a | `C of [> `A of 'a ] * 'b ] as 'b) -> bool = # 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 = -- # 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 = 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