# Automated transformation into spigot algorithm?

Is there any research on transforming 'standard' algorithms into spigot algorithms?

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.

• what's a spigot algorithm ? – Suresh Venkat Feb 2 '11 at 6:25
• 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 Feb 2 '11 at 6:34
• Information on how to manually transform an algorithm to a spigot algorithm would be sufficient. – shapr Feb 2 '11 at 7:02
• 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 Feb 2 '11 at 8:05
• 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 Feb 2 '11 at 16:30

## 2 Answers

Deforestation 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, 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.

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.