<p><a href="http://homepages.inf.ed.ac.uk/wadler/topics/deforestation.html" rel="nofollow">Deforestation</a> is a technique for eliminating intermediate data structures when composing functions together (in a lazy language). It improves the memory usage of programs, and is used by the GHC Haskell compiler. </p>

<p>A more general notion is <strong><a href="https://eprints.kfupm.edu.sa/75953/1/75953.pdf" rel="nofollow">fusion</a></strong>, which combines multiple traversals of a data structure into a single traversal. Fusion rules have been developed for programs written in terms of <code>map</code> and <code>fold</code>.  (If this is the kind of thing you are looking for, I can provide some references (as can google).)</p>

<p>Other transformations can be found on the program transformation <a href="http://www.program-transformation.org/" rel="nofollow">wiki</a>.</p>

CC BY-SA 2.5
2011-02-02T16:29:34.373Z
2011-02-02T16:53:22.870Z
2011-02-02T16:53:22.870Z
Dave Clarke
<p>You're going to run into some problems automating transformation of a generic algorithm into a spigot algorithm (halting problem).  Though as far as I know, if you can write out a formula for determining the nth digit of the mth number without iterating previous numbers in order to do it, you could probably convert it to a spigot algorithm.</p>

CC BY-SA 2.5
2011-02-02T16:07:30.520Z
2011-02-02T16:07:30.520Z
Neil
<p>Is there any research on transforming 'standard' algorithms into <a href="http://en.wikipedia.org/wiki/Spigot_algorithm" rel="nofollow">spigot algorithms</a>?</p>

<p>I'd be happiest with automated transformations, but happy to learn about any research in this area.</p>

<p>For my purposes, I'd like to be able to transform a Haskell function into a spigot algorithm to improve garbage collection behavior.</p>

CC BY-SA 2.5
2011-02-02T06:25:52.020Z
what's a spigot algorithm ?
Suresh Venkat
CC BY-SA 2.5
2011-02-02T06:34:19.740Z
Are you looking for something like optimization performed by a compiler?  I do not think that an automated transformation can transform one algorithm into another.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-02T07:02:11.250Z
Information on how to manually transform an algorithm to a spigot algorithm would be sufficient.
shapr
CC BY-SA 2.5
2011-02-02T07:43:43.907Z
I'm not sure what you mean: if I have a "standard" algorithm for sorting, would you expect a spigot algorithm to output a stream of sorted elements ? that's trivially doable by storing the answer and returning the numbers on demand. I'm sure you don't mean this, but clarification would help
Suresh Venkat
CC BY-SA 2.5
2011-02-02T08:05:10.470Z
This question could use some specifics or concrete examples and especially some elaboration about why you care about the problem. It appears like you attempted to be very general in your question-asking, but then went quite far away from your original motivation. A good question doesn't need to necessarily ask for answers from the breadth and scope of all-that-is; tell us about your problem!
Daniel Apon
CC BY-SA 2.5
2011-02-02T11:29:37.267Z
@Suresh, I am not an expert but my guess is that this might be related to (pure) functional programming languages lacking memory for storing values.
Kaveh
CC BY-SA 2.5
2011-02-02T16:30:27.913Z
An example is definitely required. Some techniques do exist for improving the memory-performance of Haskell programs, but I cannot say whether they are related to spigot algorithms.
Dave Clarke
<ds.algorithms><pl.programming-languages><functional-programming>
Automated transformation into spigot algorithm?
shapr
# Automated transformation into spigot algorithm?

(Asked by: username_0 on 2011-02-02)

Is there any research on transforming 'standard' algorithms into [spigot algorithms](http://en.wikipedia.org/wiki/Spigot_algorithm)?

I'd be happiest with automated transformations, but happy to learn about any research in this area.

For my purposes, I'd like to be able to transform a Haskell function into a spigot algorithm to improve garbage collection behavior.

**Tags:** ds.algorithms, pl.programming-languages, functional-programming
> **Comments:**
> **username_1**: what's a spigot algorithm ?  
> **username_2**: Are you looking for something like optimization performed by a compiler?  I do not think that an automated transformation can transform one algorithm into another.  
> **username_0**: Information on how to manually transform an algorithm to a spigot algorithm would be sufficient.  
> **username_1**: I'm not sure what you mean: if I have a "standard" algorithm for sorting, would you expect a spigot algorithm to output a stream of sorted elements ? that's trivially doable by storing the answer and returning the numbers on demand. I'm sure you don't mean this, but clarification would help  
> **username_3**: This question could use some specifics or concrete examples and especially some elaboration about why you care about the problem. It appears like you attempted to be very general in your question-asking, but then went quite far away from your original motivation. A good question doesn't need to necessarily ask for answers from the breadth and scope of all-that-is; tell us about your problem!  
> **username_4**: @Suresh, I am not an expert but my guess is that this might be related to (pure) functional programming languages lacking memory for storing values.  
> **username_5**: An example is definitely required. Some techniques do exist for improving the memory-performance of Haskell programs, but I cannot say whether they are related to spigot algorithms.  

---

## 2 answers

### Answer by username_5 on 2011-02-02. Score: 3

[Deforestation](http://homepages.inf.ed.ac.uk/wadler/topics/deforestation.html) is a technique for eliminating intermediate data structures when composing functions together (in a lazy language). It improves the memory usage of programs, and is used by the GHC Haskell compiler.

A more general notion is **[fusion](https://eprints.kfupm.edu.sa/75953/1/75953.pdf)**, which combines multiple traversals of a data structure into a single traversal. Fusion rules have been developed for programs written in terms of `map` and `fold`. (If this is the kind of thing you are looking for, I can provide some references (as can google).)

Other transformations can be found on the program transformation [wiki](http://www.program-transformation.org/).


---

### Answer by username_6 on 2011-02-02. Score: 1

You're going to run into some problems automating transformation of a generic algorithm into a spigot algorithm (halting problem). Though as far as I know, if you can write out a formula for determining the nth digit of the mth number without iterating previous numbers in order to do it, you could probably convert it to a spigot algorithm.


---

