[Caml-list] Great Beginner

[Caml-list] Great Beginner

[Franck]

Hi!

I want to calculate the sum of the n first numbers.
I've written this code:
let x =0;;
let somme n =
        for i=1 to n
                do
                  x=x+i
                done;;

It doesn't work.
Why ?

Thanks

Franck

-- 
___________________________________
Franck Collineau
FTR&D DMI/TAM/TIL
4 rue du Clos Courtel
B.P. 59
35512 Cesson Sévigné Cedex
tél: 02 99 12 43 97
franck.collineau@francetelecom.com
___________________________________
-------------------
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

Re: [Caml-list] Great Beginner

[Diego Olivier Fernandez Pons]

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 = <fun>
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

Re: [Caml-list] Great Beginner

[Remi VANICAT]

Franck <franck.collineau@francetelecom.com> writes:

> Hi!
> 
> I want to calculate the sum of the n first numbers.
> I've written this code:
> let x =0;;
> let somme n =
>         for i=1 to n
>                 do
>                   x=x+i
>                 done;;
> 
> It doesn't work.
> Why ?

Because ocaml is a functional language, so imperative action (as x = x
+ i) doesn't work.

A mean to do this is :
let x = ref 0;;
let somme n =
  for i = 1 to n do
    x := !x + i
  done;;

but the good way to do it is more :
let rec somme n =
  if n = 0 then 0
  else n + (somme (n - 1))

let x = somme 10

or even better (with a tail recursive function) :

let somme n =
  let rec aux i x =
    if i <= n then
      aux (i+1) (x + i)
    else x in
  aux 1 0


-- 
Rémi Vanicat
vanicat@labri.u-bordeaux.fr
http://dept-info.labri.u-bordeaux.fr/~vanicat
-------------------
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

Re: [Caml-list] Great Beginner

[Remi VANICAT]

"Diego Olivier Fernandez Pons" <FernandezPons@iFrance.com> writes:

> 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)
> ;;

j'ai du mal a voir la différence entre ceci et mon code. le if then
else du caml est une construction fonctionnel.

[..]

> 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.

je vous l'accorde, mais c'est une question d'habitude ici

> 
> 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
> ;;

et en caml, on préférera (c'est quand même plus lisible) :

let somme n =
   let rec sommeCPS total = function
          | 0 -> total
          | k -> sommeCPS (total + k)  (k - 1)
   in somme CPS 0 n


les "function" partout ne rajoute absolument rien a la lisibilité,
voir même en enlève, l'information importante étant noyé au milieux de
nombreux mot clé.
-- 
Rémi Vanicat
vanicat@labri.u-bordeaux.fr
http://dept-info.labri.u-bordeaux.fr/~vanicat
-------------------
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

Re: [Caml-list] Great Beginner

[Diego Olivier Fernandez Pons]

Je devrais peut-être cesser de poster sur ce forum, je vais réussir à
me faire plus d'ennemis que ne doit raisonnablement avoir un homme.

Le but de mon message n'était pas de dire que vous ne programmiez pas
fonctionnellement, mais d'illustrer un certain nombre de
particularités des langages fonctionnels (et que ne possèdent pas tous
langages impératifs), c'est en ce sens que j'ai dit que le code que
j'exhibais était plus « fonctionnel » ; raison pour laquelle j'ai
abordé tour à tour :
  - la définition des functions avec la syntaxe lambda
  - la récursivité ascendante et descendante
  - le pattern matching et utilisation du when
  - l'instruction trace
  - les produits cartésiens
  - les fonctions locales...

Le but en était purement pédagogique (puisque le message portait pour
titre « great beginner » et que c'était vraisemblablement le cas),
d'autant plus que vous aviez déjà illustré dans votre message
précédent les structures de contrôle « if then else » et les
références.

Votre code est bien évidemment parfaitement correct.

Moi j'écris plutôt :

let somme = function n ->
   let rec sommeCPS total = function
      | 0 -> total
      | k -> sommeCPS (total + k)  (k - 1)
   in
       sommeCPS 0 n
;;

C'est juste une question de style (d'ailleurs je ne respecte pas tout
à fait la norme Caml).

        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

RE: [Caml-list] Great Beginner

[Krishnaswami, Neel]

Franck [mailto:franck.collineau@francetelecom.com] wrote:
> Hello!
> I have written the following code:
> let somme(x,n)=
>     for i=1 to i=n
>         do
>         x<-x+1
>         done;;
> 
> caml tel me that i is not define. What is the problem ?

You have a couple of syntax errors. First, the syntax of a 
for-loop is 

  "for i = 1 to n do <foo> done"

Second, your assignment statement x <- x + 1 has the wrong syntax,
and the wrong type. If you want to do an assignment, you need to 
use the (:=) operator, like this:

  x := 5

(:=) has the type 'a ref -> 'a -> unit, which means that the left
hand side should be a reference, and the right hand side should be
the value you want the reference to point to. However, when you 
write:

  x := x + 1

you will get a type error, because x has type int ref, and (+) has
type int -> int -> int. So to do the addition you need to dereference 
the reference:

let somme(x, n) = 
  for i = 1 to n do
    x := !x + 1
  done

which has type int ref -> int -> unit. This doesn't look like a 
function I would want to write, but maybe you do. :)

--
Neel Krishnaswami
neelk@cswcasa.com
-------------------
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

[Caml-list] Great Beginner

[Franck]

    Hello!
I have written the following code:
let somme(x,n)=
    for i=1 to i=n
        do
        x<-x+1
        done;;

caml tel me that i is not define.
What is the problem ?

Thanks

-- 
___________________________________
Franck Collineau
FTR&D DMI/TAM/TIL
4 rue du Clos Courtel
B.P. 59
35512 Cesson Sévigné Cedex
tél: 02 99 12 43 97
franck.collineau@francetelecom.com
___________________________________
-------------------
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