Using circular programs to eliminate multiple traversals of data
RS Bird - Acta informatica, 1984 - Springer
RS Bird
Acta informatica, 1984•SpringerThis paper describes a technique for transforming functional programs that repeatedly
traverse a data structure into more efficient alternatives that do not. The transformation
makes essential use of lazy evaluation and local recursion (such as provided by letrec, or its
equivalent) to build a circular program that, on one pass over the structure, determines the
effects of the individual traversals and then combines them.
traverse a data structure into more efficient alternatives that do not. The transformation
makes essential use of lazy evaluation and local recursion (such as provided by letrec, or its
equivalent) to build a circular program that, on one pass over the structure, determines the
effects of the individual traversals and then combines them.
Summary
This paper describes a technique for transforming functional programs that repeatedly traverse a data structure into more efficient alternatives that do not. The transformation makes essential use of lazy evaluation and local recursion (such as provided by letrec, or its equivalent) to build a circular program that, on one pass over the structure, determines the effects of the individual traversals and then combines them.
Springer