Tupling

1 definition found

From The Free On-line Dictionary of Computing (27 SEP 03) [foldoc]:

  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)