Fonction de somme tail-recursive

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.

Maintenant, je voudrais que la fonction soit tail-recursive (je ne suis pas sûr du terme français).

On dit "récursive terminale".

Décidément, je me les paye à chaque fois, les pièges classiques.

Oui, bien sûr, c'était à titre d'exercice ici.

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

Ce n'est pas l'avis de mon prof d'info !

Je suis assez d'accord avec Vayel. Je pense que c'est juste la notation des fonctions qui me joue des tours.

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 !

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.

C'est plutôt quelque chose comme f a+b (surtout écrit comme ça) qui a tendance à me faire oublier qu'il s'agit de (f a)+b. Exactement comme dans mon message initial, en fait.

Ça ne change rien au fait que l'application (f a) soit prioritaire sur le reste.

Non bien sûr, mais je trouve ça assez transparent dans f a + f b ; je me vois mal comprendre f (a+f b) ou autre chose.

Mais si mais si, ça vient avec l'habitude.

Une solution pour éviter d'être trompé par ce genre d'écriture est de choisir de toujours mettre une espace avant et après un opérateur. En plus c'est plus joli.

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.

Je trouve ça moche le double arobase et je préfère le simple $ en Haskell.

1

let ($) = (@@)

Voilà.

Pas tout à fait. x @@ y @@ z est x (y z), comme le $ de haskell. x $ y $ z est (x y) z.

Heu. Non. http://stackoverflow.com/a/1290727

Tu dois penser à (.).

Dab, le lien que tu donnes confirme ce que je dis. . en haskell, c'est autre chose, c'est pour composer des fonctions. Il n'y a pas d'équivalent standard en OCaml.