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

The need to specify 'rec' in a recursive function defintion
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2010-02-09 (22:16) From: Saptarshi Guha Subject: Re: [Caml-list] The need to specify 'rec' in a recursive function defintion
```>
> let f arg = expr
>
> is just a short-hand notation for
>
> let f = (fun arg -> expr)
>
> or, in other words, the anonymous function constructor (fun arg -> expr)
> is the basic building block to which the "let" construction is broken
> down. The anonymous function has a direct counterpart in the lambda
> calculus, i.e. this is the level of mathematical groundwork.

>
> You cannot directly express recursion in an anonymous function. For
> defining the operational meaning of a recursive function a special
> helper is needed, the Y-combinator. It gets quite complicated here from
> a theoretical point of view because the Y-combinator is not typable. But
> generally, the idea is to have a combinator y that can be applied to a
> function like
> Â  y (fun f arg -> expr) arg
> and that "runs" this function recursively, where "f" is the recursion.

This makes sense. Thanks, I did read about the y-combinator and its
use in recursion in Friedman and Wand. I'll read it again.

Thanks for the help
Saptarshi

```