Loading ...
Sorry, an error occurred while loading the content.
 

type signature indicating a function is not tail recursive

Expand Messages
  • Francois Berenger
    Hello, 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
    Message 1 of 2 , Oct 2, 2011
      Hello,

      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.

      Regards,
      F.
    • Gabriel Scherer
      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
      Message 2 of 2 , Oct 2, 2011
        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:
        > Hello,
        >
        > 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.
        >
        > Regards,
        > F.
        >
        >
        > ------------------------------------
        >
        > 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
        >
        >
        >
        >
      Your message has been successfully submitted and would be delivered to recipients shortly.