ocaml:List
Un article de Polydoc.
Sommaire |
[modifier] Description
Certaines fonctions sont dites non récursives terminales (tail-recursive). Une fonction tail-rec utilise un espace de pile constant tandis qu'une fonction non tail-rec utilise un espace de pile proportionnel à la longueur de la liste passée en argument, ce qui peut poser problème avec de très longues listes. Quand la fonction prends plusieurs listes en argument un formule donnant approximativement l'espace pile utilisé (dans une unité non spécifié :S) est affichée entre parenthèses. L'indication ci-dessus peut néanmoins être ignorée si la liste comporte moins de 10000 éléments.
[modifier] Fonctions
[modifier] length
'a list -> int
Retourne le nombre d'élément de la liste passé en argument.
[modifier] hd
'a list -> 'a
Retourne le premier élément de la liste.
[modifier] tl
'a list -> 'a list
Retourne la liste sans son premier élément.
[modifier] nth
'a list -> int -> 'a
Retourne l'élément d'index n de la liste, sachant que le premier élément de la liste est à la position zéro et le dernier à length-1.
[modifier] rev
'a list -> 'a list
Renvoie l'inverse de la liste passée en argument.
Exemple :# List.rev [1;2;3];; - : int list = [3;2;1]
[modifier] append
'a list -> 'a list -> 'a list
Ajoute une élément à une autre liste.
/!\ Attention : Cette fonction n'est pas tail-rec Cette fonction est similaire à l'opérateur @ qui n'est pas non plus tail-rec.
Exemple :# List.append [1;2;3] [4;5;6];; - : int list = [1;2;3;4;5;6]
[modifier] rev_append
'a list -> 'a list -> 'a list
Cette fonction ajoute l'inverse de la premier liste passée en argument et l'ajoute à la deuxième, cette fonction est similaire à List.rev l1 @ l2 mais est tail-rec et a un meilleur rendement.
[modifier] concat
'a list list -> 'a list
Concaténe une liste de lists. Les éléments de l'argument sont tous concaténés dans le même ordre pour donner le résultat. Concatenate a list of lists. The elements of the argument are all concatenated together (in the same order) to give the result. Cette fonction n'est pas tail-rec (taille de l'argument + taille de la sous-liste la plus longue).
Exemple :# List.concat [[1;2;3];[4;5];[6;7;8;9]];; - : int list [1;2;3;4;5;6;7;8;9]
[modifier] flatten
'a list list -> 'a list
Identique à concat.
[modifier] iter
('a -> unit) -> 'a list -> unit
List.iter f \[a1; ...; an\] applique la fonction f à tous les éléments de la liste en commençant par a1 et en finissant par an. C'est équivalent à begin f a1; f a2; ...; f an; () end.
[modifier] map
('a -> 'b) -> 'a list -> 'b list
De même qu'iter cette fonction applique une fonction à chaque élément de la liste mais elle retourne le résultat sous forme de liste.
Cette fonction n'est pas tail-rec.
__Exemple :__ # List.map (fun x->x*2) [1;2;3];;
- : int list [2;4;6]
[modifier] rev_map
('a -> 'b) -> 'a list > 'b list
Cette fonction est identique à List.rev (List.map f \[a1; ...; an\]) mais elle est tail-rec et a un meilleur rendement.
[modifier] fold_left
('a -> 'b -> 'a) -> 'a -> 'b list -> 'a List.fold_left f a \[b1; ...; bn\] est en fait : f (... (f (f a b1) b2) ...) bn.
Exemple :# List.fold_left (fun x -> fun y -> x+y) 1 [1;2;3];; - : int = 7
[modifier] fold_right
('a -> 'b -> 'b) -> 'a list -> 'b -> 'b
List.fold_right f \[a1; ...; an\] b est en fait f a1 (f a2 (... (f an b) ...)). Cette fonction n'est pas tail-rec.
Exemple :# List.fold_right (fun x -> fun y -> x+y) [1;2;3] 1;; - : int = 7
Vous pouvez donc vous demander : où est la différence entre fold_left et fold_right et bien en fait prenez l'exemple suivant et vous comprendrez que l'ordre d'évaluation des éléments est important :
[modifier] iter2
('a -> 'b -> unit) -> 'a list -> 'b list -> unit List.iter2 f \[a1; ...; an\] \[b1; ...; bn\] correspond à f a1 b1; ...; f an bn. Renvoie l'erreur : __Invalid_argument__ si les listes n'ont pas la même longueur.
[modifier] map2
('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list List.map2 f \[a1; ...; an\] \[b1; ...; bn\] correspond à \[f a1 b1; ...; f an bn\]. Renvoie l'erreur __Invalid_argument__ si les deux listes ont des longueurs différentes. n'est pas tail-rec.
