Re: [Caml-list] The need to specify 'rec' in a recursive function defintion

[Saptarshi Guha <saptarshi.guha@gmail.com>]

>
> 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