Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456
Stream Fusion: From Lists to Streams to Nothing at All
[go: Go Back, main page]
Blue PiLlS

Stream Fusion

From Lists to Streams to Nothing at All

Duncan Coutts1, Roman Leshchinskiy2 and Don Stewart2.

1Programming Tools Group
Oxford University Computing Laboratory

2Computer Science & Engineering
University of New South Wales

Accepted for ICFP 2007.

Abstract

This paper presents an automatic fusion system, stream fusion, based on equational transformations, that fuses a wider range of functions than existing short-cut fusion systems. In particular, stream fusion is able to fuse zips, left folds and functions over nested lists, including list comprehensions. A distinguishing feature of the stream fusion framework is its simplicity: by transforming list functions to expose their structure, intermediate values are eliminated by general purpose compiler optimisations.

We have reimplemented the entire Haskell standard list library on top of our framework, providing stream fusion for Haskell lists. By allowing a wider range of functions to fuse, we see an increase in the number of occurrences of fusion in typical Haskell programs. We present benchmarks documenting time and space improvements.

Full Text

The full text of the paper can be downloaded: (ps.gz ,pdf)

Source code

The source code for the Data.Stream library, and examples used in the paper, can be downloaded from the project website.

BibTeX Entry

@inproceedings{CLS07,
    author = {Duncan Coutts and Roman Leshchinskiy and Don Stewart},
    title  = {Stream Fusion: From Lists to Streams to Nothing at All},
    booktitle = {Proceedings of the ACM SIGPLAN International Conference on Functional Programming, ICFP 2007},
    year   = 2007,
    month  = apr,
    note   = "To appear"
}
Mon Jul 23 13:22:59 EST 2007