From: rossberg@mpi-sws.org
To: caml-list@yquem.inria.fr
Subject: Re: [Caml-list] The need to specify 'rec' in a recursive function defintion
Date: Wed, 10 Feb 2010 11:12:34 +0100 (CET) [thread overview]
Message-ID: <35ebacb77d7cfe3694edbada6ce91229.squirrel@mail.mpi-sws.org> (raw)
In-Reply-To: <7d8707de1002092319j4d6bfca5s169914a992d57be2@mail.gmail.com>
"Andrej Bauer" <andrej.bauer@andrej.com> wrote:
>
> What Gerd probably meant was that the usual untyped lambda-calculus
> definition of y, which gets us recursion out of nothing isn't typeable
> because self-application requires unrestricted recursive types.
Fortunately, even that is not quite correct: Y is perfectly typable in
plain ML, you just need to introduce the recursive type it employs
explicitly:
type 'a fix = Fix of ('a fix -> 'a)
let fix f = let z = fun (Fix g' as g) x -> f (g' g) x in z (Fix z)
Now, for example:
let fac = fix (fun fac n -> if n = 0 then 1 else n * fac (n-1))
let n = fac 7
Best,
/Andreas
next prev parent reply other threads:[~2010-02-10 10:12 UTC|newest]
Thread overview: 25+ messages / expand[flat|nested] mbox.gz Atom feed top
2010-02-09 20:50 Saptarshi Guha
2010-02-09 21:55 ` [Caml-list] " Guillaume Yziquel
2010-02-09 22:14 ` Saptarshi Guha
2010-02-09 22:01 ` Gerd Stolpmann
2010-02-09 21:58 ` Guillaume Yziquel
2010-02-09 22:34 ` Gerd Stolpmann
2010-02-10 0:07 ` Guillaume Yziquel
2010-02-10 3:10 ` Alain Frisch
2010-02-09 22:16 ` Saptarshi Guha
2010-02-09 23:29 ` Jon Harrop
2010-02-10 10:15 ` rossberg
2010-02-10 7:19 ` Andrej Bauer
2010-02-10 9:36 ` Francois Maurel
2010-02-10 10:12 ` rossberg [this message]
2010-02-09 23:33 ` Jon Harrop
2010-02-09 22:31 ` Saptarshi Guha
2010-02-10 0:12 ` Jon Harrop
2010-02-10 22:01 ` Stefan Monnier
2010-02-10 22:25 ` [Caml-list] " Till Varoquaux
2010-02-11 1:48 ` Jon Harrop
2010-02-15 15:46 ` Stefan Monnier
2010-02-15 17:33 ` [Caml-list] " Jon Harrop
2010-02-15 20:36 ` Stefan Monnier
2010-02-16 14:42 ` Stefan Monnier
2010-02-16 16:21 ` [Caml-list] " Ashish Agarwal
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=35ebacb77d7cfe3694edbada6ce91229.squirrel@mail.mpi-sws.org \
--to=rossberg@mpi-sws.org \
--cc=caml-list@yquem.inria.fr \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).