Data Flow Fusion with Series Expressions in Haskell

Existing approaches to array fusion can deal with straight-line pro-ducer consumer pipelines, but cannot fuse branching data flows where a generated array is consumed by several different con-sumers. Branching data flows are common and natural to write, but the lack of fusion leads to the creation of an intermediate array at every branch point. We present a new array fusion system that handles branches, based on Waters’s series expression framework, but extended to work in a functional setting. Our system also solves a related problem in stream fusion, namely the introduction of du-plicate loop counters. We demonstrate speedup over existing fusion systems for several key examples. Categories and Subject Descriptors D.3.3 [Programming Lan