Reflection without Remorse: Revealing a hidden sequence to speed up monadic reflection

Abstract : A series of list appends or monadic binds for many monads per- forms algorithmically worse when left-associated. Continuation- passing style (CPS) is well-known to cure this severe dependence of performance on the association pattern. The advantage of CPS dwindles or disappears if we have to examine or modify the inter- mediate result of a series of appends or binds, before continuing the series. Such examination is frequently needed, for example, to control search in non-determinism monads. We present an alternative approach that is just as general as CPS but more robust: it makes series of binds and other such opera- tions efficient regardless of the association pattern – and also pro- vides efficient access to intermediate results. The key is to represent such a conceptual sequence as an efficient sequence data structure. Efficient sequence data structures from the literature are homoge- neous and cannot be applied as they are in a type-safe way to series of monadic binds. We generalize them to type aligned sequences and show how to construct their (assuredly order-preserving) im- plementations. We demonstrate that our solution solves previously undocumented, severe performance problems in iteratees, LogicT transformers, free monads and extensible effects
Type de document :
Communication dans un congrès
Haskell '14 - Proceedings of the 2014 ACM SIGPLAN symposium on Haskell, Sep 2014, Gothenburg, Sweden. ACM, pp.133-144, 〈10.1145/2633357.2633360〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01110936
Contributeur : Anne Jaigu <>
Soumis le : jeudi 29 janvier 2015 - 11:33:41
Dernière modification le : mercredi 20 décembre 2017 - 17:42:07

Identifiants

Collections

Citation

Atze Van Der Ploeg, Oleg Kiselyov. Reflection without Remorse: Revealing a hidden sequence to speed up monadic reflection. Haskell '14 - Proceedings of the 2014 ACM SIGPLAN symposium on Haskell, Sep 2014, Gothenburg, Sweden. ACM, pp.133-144, 〈10.1145/2633357.2633360〉. 〈hal-01110936〉

Partager

Métriques

Consultations de la notice

103