Discussion :

[lucci57]

bonjour
j'ai fais une fonction récursif en ocaml qui inverse une liste mais il a une erreur et je ne comprend pas la cause:voisi le code

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
let rec rev l=match l with
  [] -> failwith "la liste est vide!"
  |h::[] ->h
  |h::t ->rev t @ h;;

voisi le résultat:
'a list list -> 'a list = <fun>

@ pour concaténer 2 listes


la question:pourquoi le parametre l est pour lui de type 'a list list,il doit etre de type 'a list.
et comment je peut corriger cette erreur.

[Dinoosaure]

On va faire point par point. La première chose, c'est que dans ce genre de situation, on préfère utiliser le mot-clé function que utilisé la construction match ... with sur le dernier argument de la fonction.

Grosso-modo, on peut considérer que ces deux codes sont équivalent:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
let f a = match a with
| ...
| ...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
let f = function
| ...
| ...

Ensuite, il faut reprendre la logique du code pour comprendre ce qui va pas. Le déstructeur h :: t sépare une list en deux élément. Sa tête h et sa queue t. Pour une liste [0; 1; 2], h voudra 0 tandis que t voudra [1; 2]. Maintenant, l'opérateur @, lui, concatène 2 listes (il est du type 'a list -> 'a list -> 'a list). Ainsi, grâce au système d'inférence des types, tu exiges à ce que la tête h soit du type 'a list puisque tu l'utilise avec @. Si nous voulons une fonction dont la signature est 'a list -> 'a list, nous devrions avoir ceci plutôt:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
let rec rev = function
| [] -> [] (* le rev d'une liste vide est une liste vide, pas besoin de lever une exception *)
| h :: t -> rev t @ [h]

Cependant, ce code, même si il fonctionne, il est lent. En effet, la complexité de l'opérateur de concaténation est de O(n), ainsi, la complexité de ton rev et de O(n²). Ce que je conseille en général aux personnes cherchant à faire cette fonction, c'est de refaire la fonction rev_append. Elle permet d'avoir spontanément une complexité O(n) et la fonction rev n'est qu'un cas particulier de rev_append.

Ou sinon, tu peux te renseigner sur les transformations que l'on peut faire sur les fonctions récursives pour quelles deviennent tail récursif ! Voilà, bonne chance.

[prgasp77]

Bonjour lucci57. Les conseils de Dinoosaure sont particulièrement bons, je te suggère de les suivre. Pour t'en persuader voici une « trace » de ce que tu cherches à faire face à ce qui serait « logique » de faire.

rev [0;1;2;3]
= (rev [1;2;3]) @ [0]
= (rev [2;3] @ [1]) @ [0]
= ((rev [3] @ [2]) @ [1]) @ [0]
= (([3] @ [2]) @ [1]) @ [0]
= ([3; 2] @ [1]) @ [0]
= ({3 :: ([2] @ [1])) @ [0]
= (3 :: [2; 1]) @ [0]
= [3;2;1] @ [0]
= 3 :: ([2;1] @ [0])
= 3 :: (2 :: ([1] @ [0]))
= 3 :: (2 :: [1;0])
= 3 :: [2;1;0]
= [3;2;1;0]

rev_append [0;1;2;3] []
= rev_append [1;2;3] [0]
= rev_append [2;3] [1;0]
= rev_append [3] [2;1;0]
= rev_append [] [3;2;1;0]
= [3;2;1;0]

Il ne te restes plus qu'à coder cette fonction que l'on appelle rev_append. rev_append l1 l2 concatène l1 inversée à la fin de l2. rev_append l1 l2 produit le même résultat que l2 @ (rev l1) mais en bien plus efficace. Comme l'a dit Dinoosaure, on défini généralement rev l1 comme rev_append l1 [].

Cdlt,