English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

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-10 (10:12)
From: rossberg@m...
Subject: Re: [Caml-list] The need to specify 'rec' in a recursive function defintion
"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

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