Deforestation and Program Fusion
summary
Explains how GHC uses rewrite rules to eliminate intermediate lists so high‑level code runs like hand‑tuned loops: foldr/build fusion turns map+sum into a single recursion, the naïve version is about half as fast on a million‑element list, and stream fusion replaces list traversal with an iterator‑style state machine to remove allocations; vector backends compile into tight C‑style loops (benchmarks show ~700µs and tiny heap usage). The repo contains the code and core dumps.
AI-written summary · about
chapters (4)
- 0:00Start
- 0:10SLAMDATA
- 0:31DEFORESTATION AND PROGRAM FUSION: APPLYING EQUATIONAL TRANSFORMS TO AUTOMATICALLY SIMPLIFY PROGRAMS
- 54:34ROBOT OVERLORD
related talks
23mDeep Fusion for Efficient Nested Recursive Computations
38mRefactoring Recursion
40mSuperfusion: Eliminating Intermediate Data Structures via Inductive Synthesis
01h 38mGHC Core Optimisations
01h 00mCause and Effect(s): Towards a More Programmable Haskell
19mCompile-Time Java Stream Fusion via mapMulti
29mStaging Automatic Differentiation with Fusion
16mCompile-Time Java Stream Fusion via mapMulti