Efficient Monadic Streams
Josef David Svenningsson, Emil Axelsson, Anders Persson, Peter Jönsson · 2015
Abstract. Functional stream representations allow for a high-level, com-positional way of programming digital signal processing algorithms. How-ever, some algorithms, such as filters, cannot be efficiently implemented using purely functional techniques, due to excessive copying of data. We present a monadic representation of stream which introduces the ability to use mutation for efficiency when implementing algorithms. Still, our representation enjoys many of the benefits of purely functional streams, such as a functional API and fusion. Our representation enables further optimizations: we show how to remove duplicate loop variables, and how to keep buffers entirely in references. The representation has been evaluated in the context of the Feldspar embedded DSL, and our measurements show that our new monadic representation consistently outperforms the functional representation by at least a factor of four.