کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6873832 | 1440706 | 2018 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Complexity bounds for container functors and comonads
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Abbott et al.'s notion of containers characterises a subset of parametric data types which can be described by a set of shapes and set of positions for each shape. This captures common data types such as tuples, lists, trees, arrays, and graphs. Various useful categorical structures can be derived for containers given additional information. For example, directed containers give rise to container comonads (Ahman et al.). Containers provide a useful reasoning principle and asbtraction mechanism for programming. This paper studies the performance characteristics of traversal schemes over containers, modelled by functor and comonad structures. A cost model for container transformations is defined from which complexity bounds for the operations of container functors and comonads are derived. These bounds suggest optimisations for programs structured using these idioms. The abstract interface provided by the syntax of containers and category theory provides complexity bounds and subsequent optimisations that are implementation agnostic (machine free).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 261, Part 1, August 2018, Pages 144-158
Journal: Information and Computation - Volume 261, Part 1, August 2018, Pages 144-158
نویسندگان
Dominic Orchard,