Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
[Caml-list] "List.index" or "List.unique" functions?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2004-05-02 (15:59)
From: Brian Hurt <bhurt@s...>
Subject: Re: [Caml-list] List.rev
On Sat, 1 May 2004, Nicolas Cannasse wrote:

> > Are there automatic ways to transform non-tail-recursive functions
> > into tail-recursive ones?
> >
> > Rich.
> You can have a look at ExtLib sources. We provide tail-recursive
> implementations for each List operations (with same "little o" complexity).

This is actually quite bad advice (sorry, Nicolas)- many of the "tricks" 
we do in Ext-Lib are not for newbies.  I'm thinking specifically of the 
Obj.magic stuff.  If you find yourself doing this anywhere else, you are 
almost certainly screwing up.

There is a fairly standard set of tricks I use to turn non-tail-recursive 
functions into tail-recursive functions.  The two most important ones are:

1) build lists backwards, then reverse them when they're done.  For 
example, List.append could be implemented:
	let append alist blist =
		let revlist = List.rev_append blist (List.rev alist) in
		List.rev revlist

2) Hoist recursive calls out of try/catch clauses, introducing variables
to detect when an exception was thrown.  For example, to read all the 
lines of a channel into a list of strings, do:
	let readfile chan = 
		let rec loop accum =
			let eof, line = 
					false, (input_line chan)
					| End_of_file ->
						true, ""
			if (eof) then
				List.rev accum
				loop (line :: accum)
		loop []

"Usenet is like a herd of performing elephants with diarrhea -- massive,
difficult to redirect, awe-inspiring, entertaining, and a source of
mind-boggling amounts of excrement when you least expect it."
                                - Gene Spafford 

To unsubscribe, mail Archives:
Bug reports: FAQ:
Beginner's list: