tupling

tupling
horizontal loop combination

   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)