BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Reflection without Remorse: Revealing a hidden sequence to speed u
 p monadic reflection - Oleg Kiselyov
DTSTART:20150209T150000Z
DTEND:20150209T160000Z
UID:TALK57790@talks.cam.ac.uk
CONTACT:Raphael Proust
DESCRIPTION:A series of list appends or monadic binds for many monads perf
 orms\nalgorithmically worse when left-associated. Continuation-passing sty
 le\n(CPS) is well-known to cure this severe dependence of performance on\n
 the association pattern. The advantage of CPS dwindles or disappears\nif w
 e have to examine or modify the intermediate result of that series\nof app
 ends or binds\, before continuing the series. Such examination is\nfrequen
 tly needed\, for example\, to control search in non-determinism\nmonads.\n
 \nWe present an alternative approach that is just as general as CPS but\nm
 ore robust: it makes series of binds and other such operations\nefficient 
 regardless of the association pattern -- and also provides\nefficient acce
 ss to intermediate results. The key is to represent such\na conceptual seq
 uence as an efficient sequence data structure.\nEfficient sequence data st
 ructures from the literature are homogeneous\nand cannot be applied as the
 y are in a type-safe way to series of\nmonadic binds.  We generalize them 
 to type aligned sequences\nand show how to construct their (assuredly orde
 r-preserving)\nimplementations. We demonstrate that our solution solves pr
 eviously\nundocumented\, severe performance problems in iteratees\, LogicT
 \ntransformers\, free monads and extensible effects.
LOCATION:SS03
END:VEVENT
END:VCALENDAR