From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 5BC08BB91 for ; Sat, 29 Jan 2005 13:15:45 +0100 (CET) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j0TCFi2Z006982 for ; Sat, 29 Jan 2005 13:15:45 +0100 Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id NAA09908 for ; Sat, 29 Jan 2005 13:15:44 +0100 (MET) Received: from rproxy.gmail.com (rproxy.gmail.com [64.233.170.202]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id j0TCFhnb027763 for ; Sat, 29 Jan 2005 13:15:44 +0100 Received: by rproxy.gmail.com with SMTP id a36so555881rnf for ; Sat, 29 Jan 2005 04:15:43 -0800 (PST) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:reply-to:to:subject:mime-version:content-type:content-transfer-encoding; b=Y20EmnGzeD/7OVM1/VxXZ6jl14BPA+LyvgEDf0VXZOepWawvUNFIVlcPXI35Nfy6KWQ3HK7CQ+u5ntgob0N8LwYTqwwf0s5lck8VNANUXToYFbidSpLyTGNxDZopZb4PiHy/rzEE1ATSscfPV4CYifi+L4aJklAYkXoWQ5I2GFs= Received: by 10.38.97.70 with SMTP id u70mr266074rnb; Sat, 29 Jan 2005 04:15:43 -0800 (PST) Received: by 10.38.65.58 with HTTP; Sat, 29 Jan 2005 04:15:43 -0800 (PST) Message-ID: <7f8e92aa0501290415321a8e46@mail.gmail.com> Date: Sat, 29 Jan 2005 14:15:43 +0200 From: Radu Grigore Reply-To: Radu Grigore To: caml-list Subject: cyclic types Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit X-Miltered: at concorde with ID 41FB7E71.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at nez-perce with ID 41FB7E6F.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; abbreviation:01 annotations:01 compiler:01 minor:01 rec:01 failwith:01 rec:01 iter:01 func:01 func:01 iter:01 failwith:01 blabla:01 expression:01 compile:01 X-Spam-Checker-Version: SpamAssassin 3.0.0 (2004-09-13) on yquem.inria.fr X-Spam-Status: No, score=0.0 required=5.0 tests=RCVD_BY_IP autolearn=disabled version=3.0.0 X-Spam-Level: Why are cyclic types forbidden? I was forced to use the definition: type forest = Forest of forest StringMap.t | Empty where I would have rather used type forest = forest StringMap.t The error is: The type abbreviation tree is cyclic I can see that the later would require type annotations such as StringMap.empty : forest because otherwise the compiler could never infer that some expression has type forest. But this is a rather minor nuisance compared to the need to match Forest/Empty all over the place. You could write: let rec make n sf = match n, sf with [], [] -> StringMap.empty : forest | nh :: nt, sfh :: sft -> let m = make nt sft in StringMap.add nh sfh m | _ -> failwith "n and sf should have the same number of elements";; let rec iter func frst = let nf el sub_frst = func el; iter func sub_frst in StringMap.iter nf frst;; Instead of what you need to write now: let rec make n sf = match n, sf with [], [] -> Empty | nh :: nt, sfh :: sft -> begin match make nt sft with Empty -> Forest (StringMap.add nh sfh StringMap.empty) | Forest m -> Forest (StringMap.add nh sfh m) end | _ -> failwith "blabla..";; let rec iter func frst = let nf el sub_frst = func el; iter func sub_frst in match frst with Empty -> () | Forest m -> StringMap.iter nf m;; It feels strange to be forced to explicitly treat the case of an empty map, which is what actually happens in the code that compiles. The first version of make/iter seems better, but it does not compile :( Also, the type definition type forest = forest StringMap.t option fails with the same error (cyclic type) although it looks a lot like the version that works. Why? -- regards, radu http://rgrig.idilis.ro/