From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id AAA26097; Mon, 12 Nov 2001 00:42:40 +0100 (MET) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id AAA26096 for ; Mon, 12 Nov 2001 00:42:38 +0100 (MET) Received: from transmail12.infosources.fr (transmail12.infosources.fr [212.232.33.78]) by concorde.inria.fr (8.11.1/8.10.0) with ESMTP id fABNgbn09753 for ; Mon, 12 Nov 2001 00:42:37 +0100 (MET) Received: from infonie.fr (mailbox.infonie.fr [195.242.64.77]) by transmail12.infosources.fr (8.11.6/8.11.6) with SMTP id fABNgb110635 for ; Mon, 12 Nov 2001 00:42:37 +0100 (MET) Received: from Utilisateur ( Unverified [212.232.44.45] ) by infonie.fr with SMTP id 27291.2513435.1121847; Mon, 12 Nov 2001 00:42:36 +0100 Message-ID: <005c01c16b0a$3971f860$2d2ce8d4@Utilisateur> From: "Diego Olivier Fernandez Pons" To: "Caml" References: <3BEBDDCA.1060307@francetelecom.com> <87hes1tubf.dlv@wanadoo.fr> Subject: Re: [Caml-list] Great Beginner Date: Sat, 10 Nov 2001 16:29:05 +0100 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 8bit X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 5.50.4133.2400 X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4133.2400 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Rémi Vanicat a proposé le code suivant : let rec somme n = if n = 0 then 0 else n + (somme (n - 1)) let somme n = let rec aux i x = if i <= n then aux (i+1) (x + i) else x in aux 1 0 Ce code reste néanmoins très proche du code impératif. Dans un style beacoup plus fonctionnel on aura plutôt : let rec somme = function | 0 -> 0 | k -> k + somme (k-1) ;; La première ligne s'assure que la récurrence descendante se terminera correctement, la deuxième définit cette récurrence. On appelle cette définition par disjonction de cas le « pattern matching » très présent dans les langages fonctionnels. L'instruction #trace somme;; vous permet de voir les appels successifs de la fonction # somme <-- 3 somme <-- 2 somme <-- 1 somme <-- 0 somme --> 0 somme --> 1 somme --> 3 somme --> 6 - : int = 6 Examinons à présent la fonction récursive terminale (l'idée est d'envoyer à la fonction en paramètre à la fois le total calculé et le nombre d'étapes effectuées (ou à effectuer)) let somme1 = function n -> let rec sommeCPS = function | (total, k) when (k = n + 1) -> total | (total, k) -> sommeCPS (total + k, k + 1) in sommeCPS (0, 0) ;; le première ligne sert à arrêter la récurrence au bon moment (lorsque indice est à n+1, autrement dit on vient de calculer la somme des n premiers termes). La seconde ligne définit cette récurrence. La ligne sommeCPS (0, 0) indique que l'on commence à compter à partir de l'indice 0 et que l'on part d'un total de 0. A vrai dire, je préfère la récurrence descendante, en effet, la fonction interne sommeCPS n'est plus dépendante de la fonction extérieure puisqu'elle n'a pas à connaître n let rec sommeCPS = function | (total, k) when (k = 0) -> total | (total, k) -> sommeCPS (total + k, k - 1) ;; On peut à présent définir la fonction somme : let somme = function n -> somme (0, n) et la tracer sommeCPS pour voir son fonctionnement # val somme : int -> int = sommeCPS <-- 0, 5 sommeCPS <-- 5, 4 sommeCPS <-- 9, 3 sommeCPS <-- 12, 2 sommeCPS <-- 14, 1 sommeCPS <-- 15, 0 sommeCPS --> 15 On voit bien l'indice décrémenter tandis que le total augmente. Bien sûr, vous pouvez toujours définir sommeCPS à l'intérieur de somme pour ne pas encombrer votre espace de noms (mais alors vous ne pouvez plus la tracer) let somme = function n -> let rec sommeCPS = function | (total, k) when (k = 0) -> total | (total, k) -> sommeCPS (total + k, k - 1) in sommeCPS (0, n) ;; Enfin, je vous recommande de « commenter » votre code par des noms de variables explicites (comme total ou k plutôt que aux, acc, etc.) ; cela permet un code immédiatement compréhensible. La seule remarque supplémentaire que l'on pourrait faire est que dans les langages fonctionnels on préfère les fonctions à plusieurs arguments que les fonctions à arguments dans les produits cartésiens (ce qui ici n'est guère difficile car vous ne faites aucun test sur la variable total) let somme = function n -> let rec sommeCPS = function total -> function | 0 -> total | k -> sommeCPS (total + k) (k - 1) in sommeCPS 0 n ;; Diego Olivier ------------------- Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr