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)