Récursivité en caml

[Rockleader]

Bonsoir à tous, je me casse la tête depuis un petit moment à essayer de faire une fonction qui me parait assez bête; sauf que...j'y arrive pas :d


J'ai une fonction dont le prototype serait le suivant

iteration n f x

La fonction va donc effectuer n fois le calcul de f(x); pour cela voilà ce que j'ai codé

Code: Tout sélectionner

let rec iterer = fun n -> fun f -> fun x ->
  match n with
  0 -> x
  | _-> iterer (n-1) (f) f(x);;

Si n vaut 0, je retourne l'argument par définition
Si non, je rappelle itérer avec n-1 f et le nouvel argument f(x)


Mais d'après l'interpréteur j'ai une erreur de type; et j'avoue ne pas comprendre pourquoi ni comment corriger le problème.

Code: Tout sélectionner

Error: This expression has type 'a but an expression was expected of type
         'a -> 'a

PS: L’intérêt est d'utiliser la récursivité hein^^


Une idée ? :hein:

[joel76]

Bonjour

Je crois que la syntaxe de Caml est très proche de celle du F#.
En F# j'ai essayé ceci :

Code: Tout sélectionner

let rec iterer = fun n -> fun f -> fun x ->
  match n with
  0 -> x
  | _-> iterer (n-1) f (f x)


Par exemple pour la fonction : let fonc (x : int) : int = x * x et l'appel en F# printfn "%A" ((iterer 3 fonc) 2) j'obtiens 256 !

J'espère que ça correspond en Caml :hum:

[Rockleader]

Bonjour

Je crois que la syntaxe de Caml est très proche de celle du F#.
En F# j'ai essayé ceci :

Code: Tout sélectionner

let rec iterer = fun n -> fun f -> fun x ->
  match n with
  0 -> x
  | _-> iterer (n-1) f (f x)


Par exemple pour la fonction : let fonc (x : int) : int = x * x et l'appel en F# printfn "%A" ((iterer 3 fonc) 2) j'obtiens 256 !

J'espère que ça correspond en Caml :hum:

J'avais écris comme ça la première fois et j'ai également obtenu cette erreur de type, c'est pour ça que j'ai parenthésé f, en espérant que ça règle le problème , mais en fait non^^



EDIT: problème réglé, en fait dans ma première version j'avais écris let rect...enfin bref ça marche du coup :ptdr:






Par contre, j'en ai deux autres qui me font des caprices, d'une part la fonction ackerman

Code: Tout sélectionner

let rec ack = fun m -> fun n ->
  if(m=0) then n+1
  else
  if(m>0 && n=0) then ack (n-1) 1
  else
  if(m>0 && n>0) then [COLOR=Red]ack (m-1) (ack m (n-1))[/COLOR];;
Error: This expression has type int but an expression was expected of type
         unit

L'erreur concerne la partie en rouge





D'autre part, j'ai une autre version de itérer qui ne marche pas comme elle le devrait

Code: Tout sélectionner

let rec itererBis = fun p -> fun f -> fun x ->
  if (p x) = true then f x
  else itererBis p f (f x);;
val itererBis : ('a -> bool) -> ('a -> 'a) -> 'a -> 'a =

L'idée c'est de faire f(x) tant que le prédicat p n'est pas vérifié.


Par exemple, l'appel suivant

itererBis (fun x -> x x/2) 45;;


devrait retourner 5.

45 22 11 5 retourne 5

Sauf que, mon interpréteur me retourne la valeur 2 :mur: et je ne vois pas ce qui n'est pas bon dans la construction de ma fonction...

[joel76]

je ne sais pas d'où vient exactement l'erreur, mais j'ai rajouté un else bidon après et ça compilait, mais ce n'est pas satisfaisant.
Cette version fonctionne en F# :

Code: Tout sélectionner

let rec ack = fun m -> fun n ->
  match m, n with
  | 0, n -> n + 1
  | m, 0 when m > 0 -> ack (m - 1) 1
  | m, n when m > 0 && n > 0 -> ack (m-1) (ack m (n-1))

PS tu avais une erreur à la troisème ligne pour n = 0 c'est ack (m-1) 1 et non pas ack (n-1) 1


Pour l'autre fonction iterbis, je pense que tu devrais écrire plutôt :

Code: Tout sélectionner

let rec itererBis = fun p -> fun f -> fun x ->
  if (p x) = true then x   <===== ici c'est ton erreur
  else itererBis p f (f x)