Getting A Quick Fix On Comonads

DSpace Repository

Show simple item record

dc.contributor.advisor Mairson, Harry G. en_US
dc.contributor.author Foner, Kenneth
dc.date.accessioned 2015-05-21T19:16:28Z
dc.date.available 2015-05-21T19:16:28Z
dc.date.issued 2015 en_US
dc.identifier.uri http://hdl.handle.net/10192/30632
dc.description.abstract A piece of functional programming folklore due to Piponi provides Lo ̈b’s theorem from modal provability logic with a computational interpretation as an unusual fixed point. Interpreting modal necessity as an arbitrary Functor (in Haskell), the “type” of Lo ̈b’s theorem is inhabited by a fixed point function allowing each part of a structure to refer to the whole. However, Functor’s logical interpretation may be used to prove Lo ̈b’s theorem only by relying on its implicit functorial strength, an axiom not available in the provability modality. As a result, the well known loeb fixed point “cheats” by using functorial strength to implement its recursion. Rather than Functor, a more faithful Curry to modal logic’s Howard is a closed comonad, of which Haskell’s ComonadApply typeclass provides analogous structure. Its computational interpreta- tion permits the definition of a novel fixed point function allowing each part of a structure to refer to its own context within the whole. This construction further guarantees maximal sharing and asymp- totic efficiency superior to loeb for locally contextual computations upon a large class of structures. By adding a distributive law, closed comonads may be com- posed into spaces of arbitrary dimensionality which preserve the performance guarantees of this new fixed point. Applications of this technique include calculation of multidi- mensional “spreadsheet-like” recurrences for a variety of cellular automata. en_US
dc.format.mimetype application/pdf en_US
dc.language English en_US
dc.language.iso eng en_US
dc.publisher Brandeis University en_US
dc.rights Copyright by Kenneth Foner 2015 en_US
dc.title Getting A Quick Fix On Comonads en_US
dc.type Thesis en_US
dc.contributor.department Department of Computer Science en_US
dc.degree.name BS en_US
dc.degree.level Bachelors en_US
dc.degree.discipline Computer Science en_US
dc.degree.grantor Brandeis University, College of Arts and Sciences en_US


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search BIR


Browse

My Account