From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by yquem.inria.fr (Postfix) with ESMTP id CFDFABC37 for ; Tue, 9 Feb 2010 23:16:35 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AoMCAG9tcUvRVdzgkGdsb2JhbACDCZdVCBUBAQEBCQkMBxMDIK0eLgqBQIVSiHEBAQMFgSqCSlsEiy4 X-IronPort-AV: E=Sophos;i="4.49,438,1262559600"; d="scan'208";a="44156553" Received: from mail-fx0-f224.google.com ([209.85.220.224]) by mail2-smtp-roc.national.inria.fr with ESMTP; 09 Feb 2010 23:16:35 +0100 Received: by fxm24 with SMTP id 24so2977fxm.3 for ; Tue, 09 Feb 2010 14:16:35 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:received:reply-to:in-reply-to :references:from:date:message-id:subject:to:cc:content-type :content-transfer-encoding; bh=8Mf4jI8gVB6oYDCJHcxsAgpxdoMBR9vQOF+nbOENEFA=; b=NXQmsWiU7ksst5ky5nuXTT9SWz/MpvHYa6/f+fwvb8chz2Re5qbcs8SnX1ZrLmzOUS oCvt3idY9bug28D3Xo+ggQfe4jSgQ93uzFddnNwR7r5EaS/UMfgUuVF/Je9h4ftnqn8r 3nW03bvVz2kKaZRMZ9RU1ko9+DbyaYxfvotaI= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:reply-to:in-reply-to:references:from:date:message-id :subject:to:cc:content-type:content-transfer-encoding; b=P/OwYjvTzfLyx6wUfNY7/yIGf6Vs8kkADDNe4mLq2zyrXokCLoND7nFA6CKZG136Al D1W1Q/nNcy5/RYS0rRArT51tZKCbg53ZMhhRJOtN6BIME955W3bQKLYkGCQglEQ/wTuW JU+h+56wINkRyVh3H86wgsb4ZgeJyxvG4hYs0= MIME-Version: 1.0 Received: by 10.239.174.15 with SMTP id h15mr980190hbf.46.1265753795171; Tue, 09 Feb 2010 14:16:35 -0800 (PST) Reply-To: saptarshi.guha@gmail.com In-Reply-To: <1265752863.5482.42.camel@flake.lan.gerd-stolpmann.de> References: <1e7471d51002091250of7a686fq537a03c9401c868f@mail.gmail.com> <1265752863.5482.42.camel@flake.lan.gerd-stolpmann.de> From: Saptarshi Guha Date: Tue, 9 Feb 2010 17:16:15 -0500 Message-ID: <1e7471d51002091416s79b2485h32834c371f4fb769@mail.gmail.com> Subject: Re: [Caml-list] The need to specify 'rec' in a recursive function defintion To: Gerd Stolpmann Cc: caml-list@yquem.inria.fr Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable X-Spam: no; 0.00; recursive:01 defintion:01 expr:01 notation:01 expr:01 lambda:01 recursion:01 recursive:01 typable:01 combinator:01 recursion:01 recursively:01 caml-list:01 constructor:01 calculus:01 > > let f arg =3D expr > > is just a short-hand notation for > > let f =3D (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 > =C2=A0 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