Reflection without remorse: revealing a hidden sequence to speed up monadic reflection
Presented at the ACM SIGPLAN Haskell Symposium, Gotheburg, Sweden
A series of list appends or monadic binds for many monads performs 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 intermediate 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 operations efficient regardless of the association pattern-- and also provides 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 homogeneous 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) implementations. We demonstrate that our solution solves previously undocumented, severe performance problems in iteratees, LogicT transformers, free monads and extensible effects.
|Keywords||performance, monads, reflection, data structures|
|THEME||Software (theme 1)|
|Series||Proceedings of the ACM SIGPLAN symposium on Haskell|
|Project||End-user scripting for visual software analysis|
|Conference||ACM SIGPLAN Haskell Symposium|
van der Ploeg, A.J, & Kiselyov, O. (2014). Reflection without remorse: revealing a hidden sequence to speed up monadic reflection. In W.S Swierstra (Ed.), Proceedings of the 2014 ACM SIGPLAN symposium on Haskell (pp. 133–144). ACM.