tupling

A program transformation where several results are returned

from a single traversal of a data structure. E.g.

mean l = sum l / length l

==@#

mean l = s/n

where

(s,n) = sumLen l

sumLen [] = (0,0)

sumLen (x:xs) = (s+x, n+1)

where

(s,n) = sumLen xs

In procedural languages this technique is known as

horizontal loop combination because it uses one loop to

calculate several results.

Another form of tupling transformation is used to avoid

repeated evaluation where a function generates several

identical calls to itself. By analysing the pattern of

recursion (see descent function) it is possible to arrange

for these identical calls to share results. E.g.

fib 0 = 1

fib 1 = 1

fib n = fib (n-1) + fib (n-2)

==@#

fib n = v where (_,v) = fibt n

fibt 0 = (1,1)

fibt n = (u+v,u) where (u,v) = fibt (n-1)

(1995-01-12)