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
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 <saptarshi.guha@g...>
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