Degrading lists

Title: Degrading lists
Author: McDermott, Dylan
Piróg, Maciej
Uustalu, Tarmo
Date: 2020-09-08
Language: English
Scope: article 6
University/Institute: Reykjavik University
Háskólinn í Reykjavík
School: School of Technology (RU)
Tæknisvið (HR)
Department: Department of Computer Science
Tölvunarfræðideild (HR)
ISBN: 978-1-4503-8821-4
Series: ACM International Conference Proceeding Series;
DOI: 10.1145/3414080.3414084
Subject: Monads; Algebraic theories; Graded monads; Degrading; Lists; Theory of computation; Functional constructs; Program semantics; Algebra; Merkingarfræði; Tölvunafræði

Show full item record


D. McDermott, M. Piróg, T. Uustalu. Degrading lists. In 22nd International Symposium on Principles and Practice of Declarative Programming (PPDP ’20), September 8–10, 2020, Bologna, Italy, art. 6, 14 pp. ACM, New York, 2020. doi:10.1145/3414080.3414084


We discuss the relationship between monads and their known generalisation, graded monads, which are especially useful for modelling computational effects equipped with a form of sequential composition. Specifically, we ask if a graded monad can be extended to a monad, and when such a degrading is in some sense canonical. Our particular examples are the graded monads of lists and non-empty lists indexed by their lengths, which gives us a pretext to study the space of all (non-graded) monad structures on the list and non-empty list endofunctors. We show that, in both cases, there exist infinitely many monad structures. However, while there are at least two ways to complete the graded monad structure on length-indexed lists to a monad structure on the list endofunctor, such a completion for non-empty lists is unique.


Post-print (lokagerð höfundar)

Files in this item

This item appears in the following Collection(s)