Applicative Shortcut Fusion

Abstract. In functional programming one usually writes programs as the composition of simpler functions. Consequently, the result of a func-tion might be generated only to be consumed immediately by another function. This potential source of inefficiency can often be eliminated using a technique called shortcut fusion, which fuses both functions in-volved in a composition to yield a monolithic one. In this article we investigate how to apply shortcut fusion to applicative computations. Applicative functors provide a model of computational effects which gen-eralise monads, but they favour an applicative programming style. To the best of our knowledge, this is the first time shortcut fusion is considered in an applicative setting.