首页    期刊浏览 2024年11月14日 星期四
登录注册

文章基本信息

  • 标题:NO-GO THEOREMS FOR DISTRIBUTIVE LAWS
  • 本地全文:下载
  • 作者:Maaike Zwart ; Dan Marsden
  • 期刊名称:Logical Methods in Computer Science
  • 印刷版ISSN:1860-5974
  • 电子版ISSN:1860-5974
  • 出版年度:2022
  • 卷号:18
  • 期号:1
  • 页码:1-61
  • DOI:10.46298/lmcs-18(1:13)2022
  • 语种:English
  • 出版社:Technical University of Braunschweig
  • 摘要:Monads are commonplace in computer science, and can be composed using Beck's distributive laws. Unfortunately, finding distributive laws can be extremely difficult and error-prone. The literature contains some general principles for constructing distributive laws. However, until now there have been no such techniques for establishing when no distributive law exists. We present three families of theorems for showing when there can be no distributive law between two monads. The first widely generalizes a counterexample attributed to Plotkin. It covers all the previous known no-go results for specific pairs of monads, and includes many new results. The second and third families are entirely novel, encompassing various new practical situations. For example, they negatively resolve the open question of whether the list monad distributes over itself, reveal a previously unobserved error in the literature, and confirm a conjecture made by Beck himself in his first paper on distributive laws. In addition, we establish conditions under which there can be at most one possible distributive law between two monads, proving various known distributive laws to be unique.
  • 关键词:monads;distributive laws;compositionality;no-go theorems
国家哲学社会科学文献中心版权所有