type signature indicating a function is not tail recursive
I am looking at List inside OcamlBrowser.
I just thought it would be really cool if I can
know a function is not tail recursive just by looking
at its type signature.
- You cannot¹, and most people would consider this an danger for
encapsulation, as you can have tail-recursive versions of function
that is not implemented with tail calls in the standard library, and
wish to change one for the other without the type system noticing.
¹: I mean that, with the current libraries, the types are
indistinguishable. Of course you would be free to define your own
`type 'a nontail = Nontail of 'a;; let nontail_call (Nontail f) = f;;`
annotation wrapper and encapsulate the desired functions with it. That
would be of dubious benefit, though.
The standard library has a rather naive handling of tail-recursion :
functions that are most naturally implemented in a tail-recursive way,
such as `fold_left`, are tail-recursive, functions that are most
naturally implemented in a non-tail-recursive way, such as
`fold_right`, are not, and functions that are equally easily
implemented with both techniques, such as `length`, tend to be. Other
List libraries such as Extlib, Core and Batteries take great care --
and jump through much hoops -- to make all iterating list functions
tail-recursive, and consider it a bug if one function isn't.
On Mon, Oct 3, 2011 at 4:01 AM, Francois Berenger <berenger@...> wrote:
> I am looking at List inside OcamlBrowser.
> I just thought it would be really cool if I can
> know a function is not tail recursive just by looking
> at its type signature.
> Archives up to December 31, 2010 are also downloadable at http://www.connettivo.net/cntprojects/ocaml_beginners
> The archives of the very official ocaml list (the seniors' one) can be found at http://caml.inria.fr
> Attachments are banned and you're asked to be polite, avoid flames etc.Yahoo! Groups Links