### Abstract

Stream Fusion is a system for removing intermediate list data structures from functional programs, in particular Haskell. This entry adapts stream fusion to Isabelle/HOL and its code generator. We define stream types for finite and possibly infinite lists and stream versions for most of the fusible list functions in the theories List and Coinductive_List, and prove them correct with respect to the conversion functions between lists and streams. The Stream Fusion transformation itself is implemented as a simproc in the preprocessor of the code generator. [Brian Huffman's AFP entry formalises stream fusion in HOLCF for the domain of lazy lists to prove the GHC compiler rewrite rules correct. In contrast, this work enables Isabelle's code generator to perform stream fusion itself. To that end, it covers both finite and coinductive lists from the HOL library and the Coinductive entry. The fusible list functions require specification and proof principles different from Huffman's.]

### License

BSD License

### Topics

- Computer science/Functional programming

### Session Stream_Fusion_Code

- Stream_Fusion
- Stream_Fusion_List
- Stream_Fusion_LList
- Stream_Fusion_Examples

### Depends on

- Coinductive

### Auto-related entries

- Stream Fusion

## Cite

×

Stream_Fusion_Code-AFP

    @article{Stream_Fusion_Code-AFP,
      author  = {Andreas Lochbihler and Alexandra Maximova},
      title   = {Stream Fusion in HOL with Code Generation},
      journal = {Archive of Formal Proofs},
      month   = {October},
      year    = {2014},
      note    = {\url{https://isa-afp.org/entries/Stream_Fusion_Code.html},
                 Formal proof development},
      ISSN    = {2150-914x},
    }

Download

## Download

× Download latest

Older releases:

- Sep 13, 2023 : Isabelle2023
- Oct 27, 2022 : Isabelle2022
- Dec 14, 2021 : Isabelle2021-1
- Feb 23, 2021 : Isabelle2021
- Apr 20, 2020 : Isabelle2020
- Jun 11, 2019 : Isabelle2019
- Aug 16, 2018 : Isabelle2018
- Oct 10, 2017 : Isabelle2017
- Dec 17, 2016 : Isabelle2016-1
- Feb 22, 2016 : Isabelle2016
- May 27, 2015 : Isabelle2015
- Oct 13, 2014 : Isabelle2014
- Oct 10, 2014 : Isabelle2014