From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@sympa.inria.fr Delivered-To: caml-list@sympa.inria.fr Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by sympa.inria.fr (Postfix) with ESMTPS id F3D877FD26 for ; Mon, 16 Nov 2015 06:44:05 +0100 (CET) IronPort-PHdr: 9a23:w5db/BXISk721B+ViZoFTUU7OrvV8LGtZVwlr6E/grcLSJyIuqrYZxSFt8tkgFKBZ4jH8fUM07OQ6PC9HzFeqsbc+Fk5M7VyFDY9wf0MmAIhBMPXQWbaF9XNKxIAIcJZSVV+9Gu6O0UGUOz3ZlnVv2HgpWVKQka3CwN5K6zPF5LIiIzvjqbpq8CVPlsD1Gf1SIgxBSv1hD2ZjtMRj4pmJ/R54TryiVwMRd5rw3h1L0mYhRf265T41pdi9yNNp6BprJYYAu3SNp41Rr1ADTkgL3t9pIiy7UGCHj20+2AEX24Kvh1NCgnDpFGmD9ai+hf949B63SCbO4XcRKo4Xinqu71sTRbpjg8MLS8h7GbMh8prgeRQpxf39DJlxIuBSoyTfN9/eqfCetQWDT5LW8dVUzNGBY+UbYIJAvEdJ+tVs8/2oF5Y/kj2PhWlGO66kmwAvXTxx6Bvlrl4HA== Authentication-Results: mail2-smtp-roc.national.inria.fr; spf=None smtp.pra=bmillwood@janestreet.com; spf=Pass smtp.mailfrom=bmillwood@janestreet.com; spf=None smtp.helo=postmaster@mxout1.mail.janestreet.com Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of bmillwood@janestreet.com) identity=pra; client-ip=38.105.200.112; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="bmillwood@janestreet.com"; x-sender="bmillwood@janestreet.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail2-smtp-roc.national.inria.fr: domain of bmillwood@janestreet.com designates 38.105.200.112 as permitted sender) identity=mailfrom; client-ip=38.105.200.112; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="bmillwood@janestreet.com"; x-sender="bmillwood@janestreet.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of postmaster@mxout1.mail.janestreet.com) identity=helo; client-ip=38.105.200.112; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="bmillwood@janestreet.com"; x-sender="postmaster@mxout1.mail.janestreet.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: A0BdAABMbElWnHDIaSZehA5vBq54j1+BZCGFbwKBJQc6EgEBAQEBAQEBEAEBAQEBBhYJT4ItggcBAQEDARIRHQEBKQMLAQQLCQILDQ0dAgIiEgEFAQoSBhMSEId3AwoIAwqLXY9NgTE+MYpXcYRjAQWGMwOEXAEBAQEBAQEBAQEBAQEBAQEBAQEBEwYKhkqEfoUIgm2BRIYQDId5iDiFHYgKgVtJli+CJRIkgRcRFgGCPyOBamWFSwEBAQ X-IPAS-Result: A0BdAABMbElWnHDIaSZehA5vBq54j1+BZCGFbwKBJQc6EgEBAQEBAQEBEAEBAQEBBhYJT4ItggcBAQEDARIRHQEBKQMLAQQLCQILDQ0dAgIiEgEFAQoSBhMSEId3AwoIAwqLXY9NgTE+MYpXcYRjAQWGMwOEXAEBAQEBAQEBAQEBAQEBAQEBAQEBEwYKhkqEfoUIgm2BRIYQDId5iDiFHYgKgVtJli+CJRIkgRcRFgGCPyOBamWFSwEBAQ X-IronPort-AV: E=Sophos;i="5.20,300,1444687200"; d="scan'208";a="187627904" Received: from mxout1.mail.janestreet.com ([38.105.200.112]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 16 Nov 2015 06:44:05 +0100 Received: from tot-qpr-mailcore1.delacy.com ([172.27.56.68] helo=tot-qpr-mailcore1) by mxout1.mail.janestreet.com with esmtps (TLSv1:DHE-RSA-AES256-SHA:256) (Exim 4.82) (envelope-from ) id 1ZyCaA-00026w-W6 for caml-list@inria.fr; Mon, 16 Nov 2015 00:44:03 -0500 X-JS-Flow: external Received: by tot-qpr-mailcore1 with JS-mailcore (0.1) (envelope-from ) id BWSW0i-AAAClD-ds; 2015-11-16 00:44:02.950866-05:00 Received: from mail-lf0-f42.google.com ([209.85.215.42]) by mxgoog1.mail.janestreet.com with esmtps (UNKNOWN:AES128-GCM-SHA256:128) (Exim 4.72) (envelope-from ) id 1ZyCaA-0006b0-Le for caml-list@inria.fr; Mon, 16 Nov 2015 00:44:02 -0500 Received: by lfdo63 with SMTP id o63so80217998lfd.2 for ; Sun, 15 Nov 2015 21:44:01 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=janestreet.com; s=google; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-type; bh=Hbz5oXaa7PCkw6xyDuAosnws/MjAH09mm7EhlwQuhFw=; b=Pa4nArraLkBmJczCyaEPbjF/TM57B/PvAQXTgQhGodujvophiWsuduLzrOuHh8DyYQ 8eQHsa3ciAybV25ShIEZHWtTFcRFuurcLMp5nzbJTpF5bKvS4YNDXmTJUnbMGc4stRRQ uCZUk+K3V+84+QA9w7WSKVPVTN3RFW5OxkJn0= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc:content-type; bh=Hbz5oXaa7PCkw6xyDuAosnws/MjAH09mm7EhlwQuhFw=; b=Wo6ilzyold+H4X4tPbeEprxNW4AVGOgaZQRH1GJOPZENwJUqKO5ZXpCD/cAoVV6Wec WTPg+yePF4kMGfjJkd+xwsqdfK2r08tDTr63oubQtd6tdn8okRNLU8m+8Kut2NiUCuLv uyEKD4LsLg+9zlJYz56PxsGQPC3iBIVEyRRRWs36V4czLEv9JZovAguLKa5mmnpCznGz 664ASUZ451ipj9463BImHKSZu5/b6uiqi36Tui75JsViYavOFe+NohdWDnt7bsoi8tgA 41QpJXQHrc1dB5GrNjkEfsW334s041xMg+VJwAX1RVKOOT+f3fI6r9Kfenej3fBkm0dO rOMA== X-Gm-Message-State: ALoCoQmiAVF0Na5lZHk2EZ1Qp0zLkBqu9k4T1sHhkzZicXyxNZaLjW1rCLtV1y6zlL3Yg1ySMMXnEd2X/7djC1/RqiOZ16mqsLz3aY3eShhRv0mjfECUd01cO7UV+DQjXNIq48Y271+g X-Received: by 10.25.15.101 with SMTP id e98mr15246014lfi.49.1447652641627; Sun, 15 Nov 2015 21:44:01 -0800 (PST) X-Received: by 10.25.15.101 with SMTP id e98mr15246009lfi.49.1447652641465; Sun, 15 Nov 2015 21:44:01 -0800 (PST) MIME-Version: 1.0 Received: by 10.25.137.85 with HTTP; Sun, 15 Nov 2015 21:43:42 -0800 (PST) In-Reply-To: <5645F28B.9000708@cryptosense.com> References: <5645DC49.7050106@tu-berlin.de> <5645E255.5060900@freenet.de> <5645E9B4.9080007@cryptosense.com> <5645F28B.9000708@cryptosense.com> From:Ben Millwood Date: Mon, 16 Nov 2015 13:43:42 +0800 Message-ID: To:Romain Bardou Cc:caml users , =?UTF-8?Q?Daniel_B=C3=BCnzli?= Content-Type: multipart/alternative; boundary=001a113f8ffa7406ec0524a1e5bd X-JS-Processed-by: mailcore X-Sender-Copy: hkg-copy Subject: Re: [Caml-list] Cyclic type abbreviation --001a113f8ffa7406ec0524a1e5bd Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable To be clear, options aren't being handled differently from any other *pre-existing* user-defined type. utop # type 'a my_type =3D One of 'a | Two of 'a * 'a;; type 'a my_type =3D One of 'a | Two of 'a * 'a utop # type node =3D int * tree * tree and tree =3D node my_type;; Error: The type abbreviation node is cyclic Using a real ADT instead of a type abbrevation works. David Allsopp already gave one way you can do it, here is another which preserves the use of the option type: utop # type node =3D Node of int * tree * tree and tree =3D node option;; type node =3D Node of int * tree * tree and tree =3D node option Note that here [tree] is still a type abbreviation, but [node] is not, so the cycle is not a problem. Note also that your original example works fine with the -rectypes flag. But my general opinion is that if you need -rectypes to compile your code, you should write different code :) On 13 November 2015 at 22:24, Romain Bardou wrote: > On 13/11/2015 14:46, Romain Bardou wrote: > >> On 13/11/2015 14:37, David Allsopp wrote: >> >>> Mr. Herr wrote: >>> >>>> On 13.11.2015 13:49, Christoph H=C3=B6ger wrote: >>>> >>>>> Dear all, >>>>> >>>>> why is this type cyclic? >>>>> >>>>> type node =3D int * tree * tree >>>>> and tree =3D node option >>>>> >>>>> I cannot introduce a manifest for the option type, as there is no >>>>> Option module (why is that, btw?) - so I would assume option to be >>>>> special enough to be handled like any other algebraic data type. >>>>> >>>> type 'a option =3D None | Some 'a >>>> >>>> no need for a module, just a simple type. Maybe you confound it with >>>> other >>>> languages. >>>> >>>> And cyclic - well, the types are referring to each other. >>>> >>>> Summary: what is supposedly wrong with it? >>>> >>> >>> I expect that what is wrong is that you can write: >>> >>> type node =3D int * tree * tree >>> and tree =3D Some of node >>> | None >>> >>> I don't know why you can't write [and tree =3D node option] instead. >>> >>> >>> David >>> >>> >> Interestingly, this definition is accepted: >> >> type tree =3D (int * 'a * 'a) option as 'a >> >> Here you are helping the type-checker because you give it a "canonical" >> representation that it can use when unifying; it no longer has to expand >> the type, potentially infinitely. I think the main point is that the >> type is isorecursive, but I'm not really an expert on the subject. >> >> > My bad, I had actually redefined the option type as a polymorphic variant > before: > > type 'a option =3D [ `None | `Some of 'a ] > > and I forgot about it when I tested the definition of tree above. > > So yeah you can do that with polymorphic variants even though they are > kind of type abbreviations. > > Thanks to Daniel for pointing this out. > > -- > Romain > > > -- > Caml-list mailing list. Subscription management and archives: > https://sympa.inria.fr/sympa/arc/caml-list > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners > Bug reports: http://caml.inria.fr/bin/caml-bugs > --001a113f8ffa7406ec0524a1e5bd Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
To be clear, options aren't being handled differently = from any other *pre-existing* user-defined type.

ut= op # type 'a my_type =3D One of 'a | Two of 'a * 'a;;
=
type 'a my_type =3D One of 'a | Two of 'a * 'a
utop # type node =3D int * tree * tree and tree =3D node my_type;;
=
Error: The type abbreviation node is cyclic

=
Using a real ADT instead of a type abbrevation works. David Allsopp al= ready gave one way you can do it, here is another which preserves the use o= f the option type:

utop # type node =3D Node = of int * tree * tree and tree =3D node option;;
type node =3D Nod= e of int * tree * tree
and tree =3D node option
<= br>
Note that here [tree] is still a type abbreviation, but [node= ] is not, so the cycle is not a problem.

Note also= that your original example works fine with the -rectypes flag. But my gene= ral opinion is that if you need -rectypes to compile your code, you should = write different code :)

On 13 November 2015 at 22:24, Romain Bardou <romain= @cryptosense.com> wrote:
On 13/11/2015 14:46, Romain Bardou wr= ote:
On 13/11/2015 14:37, David Allsopp wrote:
Mr. Herr wrote:
On 13.11.2015 13:49, Christoph H=C3=B6ger wrote:
Dear all,

why is this type cyclic?

type node =3D int * tree * tree
=C2=A0 and tree =3D node option

I cannot introduce a manifest for the option type, as there is no
Option module (why is that, btw?) - so I would assume option to be
special enough to be handled like any other algebraic data type.
type 'a option =3D None | Some 'a

no need for a module, just a simple type. Maybe you confound it with
other
languages.

And cyclic - well, the types are referring to each other.

Summary: what is supposedly wrong with it?

I expect that what is wrong is that you can write:

type node =3D int * tree * tree
=C2=A0 and tree =3D Some of node
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0| None

I don't know why you can't write [and tree =3D node option] instead= .


David


Interestingly, this definition is accepted:

type tree =3D (int * 'a * 'a) option as 'a

Here you are helping the type-checker because you give it a "canonical= "
representation that it can use when unifying; it no longer has to expand
the type, potentially infinitely. I think the main point is that the
type is isorecursive, but I'm not really an expert on the subject.


My bad, I had actually redefined the option type as a polymorphic variant b= efore:

type 'a option =3D [ `None | `Some of 'a ]

and I forgot about it when I tested the definition of tree above.

So yeah you can do that with polymorphic variants even though they are kind= of type abbreviations.

Thanks to Daniel for pointing this out.

--
Romain


--
Caml-list mailing list.=C2=A0 Subscription management and archives:
https://sympa.inria.fr/sympa/arc/caml-list
Beginner's list: http://groups.yahoo.com/group/ocam= l_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs

--001a113f8ffa7406ec0524a1e5bd--