Encyclopedia > Tail recursion modulo cons

  Article Content

Tail recursion modulo cons

Tail recursion modulo cons is a generalisation of tail recursion introduced by D.H.D. Warren. It applies when the last thing a function does is to apply a constructor functions (e.g. cons) to an application of a non-primitive function. This is transformed into a tail call to the function which is also passed a pointer to where its result should be written. E.g.
	f []     = []
	f (x:xs) = 1 : f xs
is transformed into (pseudo C/Haskell):
	f [] = []
	f l  = f' l allocate_cons

	f' []     p = { *p = nil;
			return *p
		      }
	f' (x:xs) p = { cell = allocate_cons;
		        *p = cell;
			cell.head = 1;
			return f' xs &cell.tail
		      }
where allocate_cons returns the address of a new cons cell, *p is the location pointed to by p and &c is the address of c.

[D.H.D. Warren, DAI Research Report 141, University of Edinburgh 1980].


This article was originally based on material from FOLDOC, used with permission. Update as needed.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
DB

... major beer brewing company of New Zealand. This is a disambiguation page; that is, one that just points to other pages that might otherwise have the same name. If you ...

 
 
 
This page was created in 36.2 ms