<html xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Calibri",sans-serif;
mso-fareast-language:EN-US;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:#0563C1;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:#954F72;
text-decoration:underline;}
p.MsoPlainText, li.MsoPlainText, div.MsoPlainText
{mso-style-priority:99;
mso-style-link:"Plain Text Char";
margin:0cm;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;
mso-fareast-language:EN-US;}
span.PlainTextChar
{mso-style-name:"Plain Text Char";
mso-style-priority:99;
mso-style-link:"Plain Text";
font-family:"Calibri",sans-serif;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri",sans-serif;
mso-fareast-language:EN-US;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:72.0pt 72.0pt 72.0pt 72.0pt;}
div.WordSection1
{page:WordSection1;}
--></style>
</head>
<body lang="EN-GB" link="#0563C1" vlink="#954F72">
<div class="WordSection1">
<p class="MsoPlainText">Hi Henning,<o:p></o:p></p>
<p class="MsoPlainText" style="margin-left:36.0pt"><o:p> </o:p></p>
<p class="MsoPlainText" style="margin-left:36.0pt"> I think this is about η-expansion, which is disabled by default for<o:p></o:p></p>
<p class="MsoPlainText" style="margin-left:36.0pt"> recursive records:<o:p></o:p></p>
<p class="MsoPlainText" style="margin-left:36.0pt"> https://agda.readthedocs.io/en/v2.5.4/language/record-types.html#eta-expansion<o:p></o:p></p>
<p class="MsoPlainText" style="margin-left:36.0pt"> <o:p></o:p></p>
<p class="MsoPlainText">You are right, I forgot. Btw, one could have eta-expansion for sums but it seems that eta-expansion for records is more popular.
<o:p></o:p></p>
<p class="MsoPlainText"><span style="color:black"><o:p> </o:p></span></p>
<p class="MsoPlainText" style="margin-left:36.0pt"> Having η for recursive coinductive types would make definitional<o:p></o:p></p>
<p class="MsoPlainText" style="margin-left:36.0pt"> equality undecidable: https://cronfa.swan.ac.uk/Record/cronfa38822<o:p></o:p></p>
<p class="MsoPlainText" style="margin-left:36.0pt"> <o:p></o:p></p>
<p class="MsoPlainText" style="margin-left:36.0pt"> About the destructors, or rather what I would call observations,
<o:p></o:p></p>
<p class="MsoPlainText"><o:p> </o:p></p>
<p class="MsoPlainText">I prefer destructors because it is nicely dual to constructors.<o:p></o:p></p>
<p class="MsoPlainText"><o:p> </o:p></p>
<p class="MsoPlainText" style="margin-left:36.0pt">this<o:p></o:p></p>
<p class="MsoPlainText" style="margin-left:36.0pt"> asymmetry is there because dependencies in the domain of observations of<o:p></o:p></p>
<p class="MsoPlainText" style="margin-left:36.0pt"> coinductive types usually don't change because people use an explicit<o:p></o:p></p>
<p class="MsoPlainText" style="margin-left:36.0pt"> equality instead. For instance, instead of<o:p></o:p></p>
<p class="MsoPlainText" style="margin-left:36.0pt"> <o:p></o:p></p>
<p class="MsoPlainText" style="margin-left:36.0pt"> record List (A : Set) : <span style="font-family:"Cambria Math",serif">
ℕ</span> → Set where<o:p></o:p></p>
<p class="MsoPlainText" style="margin-left:36.0pt"> coinductive<o:p></o:p></p>
<p class="MsoPlainText" style="margin-left:36.0pt"> hd : {n : <span style="font-family:"Cambria Math",serif">
ℕ</span>} → List A (s n) → A<o:p></o:p></p>
<p class="MsoPlainText" style="margin-left:36.0pt"> tl : {n : <span style="font-family:"Cambria Math",serif">
ℕ</span>} → List A (s n) → List A n<o:p></o:p></p>
<p class="MsoPlainText" style="margin-left:36.0pt"> <o:p></o:p></p>
<p class="MsoPlainText" style="margin-left:36.0pt"> people would write<o:p></o:p></p>
<p class="MsoPlainText" style="margin-left:36.0pt"> <o:p></o:p></p>
<p class="MsoPlainText" style="margin-left:36.0pt"> record List (A : Set) (n :
<span style="font-family:"Cambria Math",serif">ℕ</span>) : Set where<o:p></o:p></p>
<p class="MsoPlainText" style="margin-left:36.0pt"> coinductive<o:p></o:p></p>
<p class="MsoPlainText" style="margin-left:36.0pt"> hd : {k : <span style="font-family:"Cambria Math",serif">
ℕ</span>} → (n == s k) → A<o:p></o:p></p>
<p class="MsoPlainText" style="margin-left:36.0pt"> tl : {k : <span style="font-family:"Cambria Math",serif">
ℕ</span>} → (n == s k) → List A k<o:p></o:p></p>
<p class="MsoPlainText" style="margin-left:36.0pt"> <o:p></o:p></p>
<p class="MsoPlainText" style="margin-left:36.0pt"> (Note that, if you change <span style="font-family:"Cambria Math",serif">
ℕ</span> to conatural numbers, then this example<o:p></o:p></p>
<p class="MsoPlainText" style="margin-left:36.0pt"> becomes more interesting).<o:p></o:p></p>
<p class="MsoPlainText"><span style="color:black"><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="color:black">Indeed. I don’t understand the argument because one could apply the dual trick for inductive types as you say yourself below.<o:p></o:p></span></p>
<p class="MsoPlainText"> <o:p></o:p></p>
<p class="MsoPlainText" style="margin-left:36.0pt"> These two types are isomorphic via an adjunction. Thus, it does not<o:p></o:p></p>
<p class="MsoPlainText" style="margin-left:36.0pt"> matter if we make the domain explicit or not, assuming that this is what<o:p></o:p></p>
<p class="MsoPlainText" style="margin-left:36.0pt"> your question was getting at.<o:p></o:p></p>
<p class="MsoPlainText" style="margin-left:36.0pt"> <o:p></o:p></p>
<p class="MsoPlainText" style="margin-left:36.0pt"> For inductive types, we prefer the first version, where dependencies in<o:p></o:p></p>
<p class="MsoPlainText" style="margin-left:36.0pt"> the codomain of constructors can change, as this simplifies pattern<o:p></o:p></p>
<p class="MsoPlainText" style="margin-left:36.0pt"> matching. The standard example there would be<o:p></o:p></p>
<p class="MsoPlainText" style="margin-left:36.0pt"> <o:p></o:p></p>
<p class="MsoPlainText" style="margin-left:36.0pt"> data Vec (A : Set) : <span style="font-family:"Cambria Math",serif">
ℕ</span> → Set where<o:p></o:p></p>
<p class="MsoPlainText" style="margin-left:36.0pt"> coinductive<o:p></o:p></p>
<p class="MsoPlainText" style="margin-left:36.0pt"> [] : Vec A 0<o:p></o:p></p>
<p class="MsoPlainText" style="margin-left:36.0pt"> _::_ : A → {n : <span style="font-family:"Cambria Math",serif">
ℕ</span>} → Vec A n → List A (s n)<o:p></o:p></p>
<p class="MsoPlainText" style="margin-left:36.0pt"> <o:p></o:p></p>
<p class="MsoPlainText" style="margin-left:36.0pt"> vs<o:p></o:p></p>
<p class="MsoPlainText" style="margin-left:36.0pt"> <o:p></o:p></p>
<p class="MsoPlainText" style="margin-left:36.0pt"> data Vec (A : Set) (n : <span style="font-family:"Cambria Math",serif">
ℕ</span>) : Set where<o:p></o:p></p>
<p class="MsoPlainText" style="margin-left:36.0pt"> coinductive<o:p></o:p></p>
<p class="MsoPlainText" style="margin-left:36.0pt"> [] : {k : <span style="font-family:"Cambria Math",serif">
ℕ</span>} → (n == 0) → Vec A n<o:p></o:p></p>
<p class="MsoPlainText" style="margin-left:36.0pt"> _::_ : A → {k : <span style="font-family:"Cambria Math",serif">
ℕ</span>} → (n == s k) → Vec A k → List A n<o:p></o:p></p>
<p class="MsoPlainText" style="margin-left:36.0pt"><o:p> </o:p></p>
<p class="MsoPlainText">My proposal is that we can should be able to write<o:p></o:p></p>
<p class="MsoPlainText"><o:p> </o:p></p>
<p class="MsoPlainText">record List (A : Set) : <span style="font-family:"Cambria Math",serif">
ℕ</span> → Set where<o:p></o:p></p>
<p class="MsoPlainText"> coinductive<o:p></o:p></p>
<p class="MsoPlainText"> destructor<o:p></o:p></p>
<p class="MsoPlainText"> hd : {n : <span style="font-family:"Cambria Math",serif">
ℕ</span>} → List A (suc n) → A<o:p></o:p></p>
<p class="MsoPlainText"> tl : {n : <span style="font-family:"Cambria Math",serif">
ℕ</span>} → List A (suc n) → List A n<o:p></o:p></p>
<p class="MsoPlainText"><o:p> </o:p></p>
<p class="MsoPlainText">That is “destructor” is an alternative to field which would be still allowed to ensure backwards compatibility.<o:p></o:p></p>
<p class="MsoPlainText"><o:p> </o:p></p>
<p class="MsoPlainText">As far as I can see copatternmatching should work nicely and we should be able to write:<o:p></o:p></p>
<p class="MsoPlainText"><o:p> </o:p></p>
<p class="MsoPlainText">map : {A B : Set} → (A → B) → {n : <span style="font-family:"Cambria Math",serif">
ℕ</span>} → List A n → List B n<o:p></o:p></p>
<p class="MsoPlainText">hd (map f x) = f (hd x)<o:p></o:p></p>
<p class="MsoPlainText">tl (map f x) = map f (tl x)<o:p></o:p></p>
<p class="MsoPlainText"><o:p> </o:p></p>
<p class="MsoPlainText">There should be no need to abuse any equality types.<o:p></o:p></p>
<p class="MsoPlainText"><o:p> </o:p></p>
<p class="MsoPlainText">Thorsten<o:p></o:p></p>
<p class="MsoPlainText" style="margin-left:36.0pt"> <o:p></o:p></p>
<p class="MsoPlainText"> <o:p></o:p></p>
<p class="MsoPlainText"> On 01/03/2020 14:19, Thorsten Altenkirch wrote:<o:p></o:p></p>
<p class="MsoPlainText"> > Hi,<o:p></o:p></p>
<p class="MsoPlainText"> > <o:p></o:p></p>
<p class="MsoPlainText"> > <o:p></o:p></p>
<p class="MsoPlainText"> > <o:p></o:p></p>
<p class="MsoPlainText"> > I am just writing some lecture notes hence I noticed something else. Why<o:p></o:p></p>
<p class="MsoPlainText"> > do we have to say coinductive when defining a recursive record, aka a<o:p></o:p></p>
<p class="MsoPlainText"> > coinductive type? This seems asymmetric because we don’t have t say<o:p></o:p></p>
<p class="MsoPlainText"> > anything when defining a recursive sum (like the natural numbers)? Is<o:p></o:p></p>
<p class="MsoPlainText"> > this just a relic from the days that records couldn’t be recursive or is<o:p></o:p></p>
<p class="MsoPlainText"> > there a technical reason?<o:p></o:p></p>
<p class="MsoPlainText"> > <o:p></o:p></p>
<p class="MsoPlainText"> > <o:p></o:p></p>
<p class="MsoPlainText"> > <o:p></o:p></p>
<p class="MsoPlainText"> > Btw, I really would like to have destructors for coinductive types<o:p></o:p></p>
<p class="MsoPlainText"> > (another asymmetry).<o:p></o:p></p>
<p class="MsoPlainText"> > <o:p></o:p></p>
<p class="MsoPlainText"> > <o:p></o:p></p>
<p class="MsoPlainText"> > <o:p></o:p></p>
<p class="MsoPlainText"> > Thorsten<o:p></o:p></p>
<p class="MsoPlainText"> > <o:p></o:p></p>
<p class="MsoPlainText"> > This message and any attachment are intended solely for the addressee<o:p></o:p></p>
<p class="MsoPlainText"> > and may contain confidential information. If you have received this<o:p></o:p></p>
<p class="MsoPlainText"> > message in error, please contact the sender and delete the email and<o:p></o:p></p>
<p class="MsoPlainText"> > attachment. <o:p></o:p></p>
<p class="MsoPlainText"> > <o:p></o:p></p>
<p class="MsoPlainText"> > Any views or opinions expressed by the author of this email do not<o:p></o:p></p>
<p class="MsoPlainText"> > necessarily reflect the views of the University of Nottingham. Email<o:p></o:p></p>
<p class="MsoPlainText"> > communications with the University of Nottingham may be monitored
<o:p></o:p></p>
<p class="MsoPlainText"> > where permitted by law.<o:p></o:p></p>
<p class="MsoPlainText"> > <o:p></o:p></p>
<p class="MsoPlainText"> > <o:p></o:p></p>
<p class="MsoPlainText"> > <o:p></o:p></p>
<p class="MsoPlainText"> > <o:p></o:p></p>
<p class="MsoPlainText"> > _______________________________________________<o:p></o:p></p>
<p class="MsoPlainText"> > Agda mailing list<o:p></o:p></p>
<p class="MsoPlainText"> > Agda@lists.chalmers.se<o:p></o:p></p>
<p class="MsoPlainText"> > https://lists.chalmers.se/mailman/listinfo/agda<o:p></o:p></p>
<p class="MsoPlainText"> > <o:p></o:p></p>
<p class="MsoPlainText"> <o:p></o:p></p>
</div>
<PRE>
This message and any attachment are intended solely for the addressee
and may contain confidential information. If you have received this
message in error, please contact the sender and delete the email and
attachment.
Any views or opinions expressed by the author of this email do not
necessarily reflect the views of the University of Nottingham. Email
communications with the University of Nottingham may be monitored
where permitted by law.
</PRE></body>
</html>