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.
performance, monads, reflection, data structures
Software (theme 1)
W.S. Swierstra
Proceedings of the ACM SIGPLAN symposium on Haskell
End-user scripting for visual software analysis
ACM SIGPLAN Haskell Symposium
Software Analysis and Transformation

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.