horizontal loop combination

1 definition found

horizontal loop combination - Free On-line Dictionary of Computing (26 May 2007) :

  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)