Fonction de somme tail-recursive

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

Bonjour,

J'essaie d'écrire une fonction sum qui retourne la somme des éléments d'une liste d'entiers. Jusque là, rien de très compliqué :

1
2
3
let rec sum = function
  | [] -> 0
  | h::t -> h + sum t;;

Maintenant, je voudrais que la fonction soit tail-recursive (je ne suis pas sûr du terme français). J'ai écrit ça :

1
2
3
4
5
6
7
let sum2 l =
  let rec loop l' acc =
    match l' with
    | [] -> acc
    | h::t -> loop t acc+h
  in
  loop l 0;;

Cependant…

1
sum2 (List.init 1000000 (Fn.id));;

ne fonctionne pas :

1
Stack overflow during evaluation (looping recursion?).

La tail-récursivité (?) est bien censée nous débarrasser du stack overflow, ou c'est encore mon cerveau qui déconne ? :(

@unidan: c'est ça, il faut les parenthèses.

Sinon, généralement pour ce genre de fonctions on préfère utiliser un fold plutôt que d'écrire explicitement la récursion.

+1 -0

Vayel : ca permet d'éviter les erreurs indétectables et incongrues, du genre faire une composée de fonction au lieu de sommer, tout en ayant une fonction qui renvoit un résultat du type qu'on attend, mais plus généralement évite ce genre de soucis ;)

Et puis quand tu commences à donner des type flèches en paramètres, c'est vite illisible sinon !

+0 -0

Il ne faut pas hésiter à abuser des parenthèses en caml ;)

unidan

Non, il faut comprendre quand elles sont nécessaires et les utiliser avec parcimonie.

En OCaml, l'application de fonction est syntaxiquement prioritaire sur le reste. Par conséquent, un morceau de code comme f a + f b est analysé comme (f a) + (f b). C'est vrai que c'est un peu déroutant au début, mais ça vient avec l'habitude.

+0 -0
Staff

Un truc que j'avais adoré dans Haskell et qu'on retrouve dans Ocaml c'est d'avoir un opérateur pou délayer la priorité de l'application. Par exemple dans le code que vous donnez :

Au lieu d'écrire :

1
f (a+b)

On peut écrire

1
f @@ a+b

Je trouve ça moche le double arobase et je préfère le simple $ en Haskell. Mais parfois c'est assez pratique et élégant je trouve.

+1 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte