String  
Nous utilisons des valeurs de type « string » presque depuis le début de ce cours. En effet, en Scheme, lorsque nous écrivons "toto", nous écrivons un « littéral string » (chaîne de caractères en français).
 
Fonctions primitives  
Dans la suite du cours, nous écrirons des définitions de fonctions qui manipulent des chaînes de caractères et, pour ce faire, nous utiliserons les primitives Scheme (i.e. les fonctions fournies par DrScheme) suivantes:
 
Pour connaitre la longueur d'une chaîne:
 
 

 
Une fonction pour concaténer des chaînes:
 
 

 
On peut considérer qu'une chaîne de caractères est une suite de caractères, le premier caractère ayant comme indice 0, le second caractère ayant comme indice 1,... et le dernier caractère ayant comme indice la longueur de la chaîne moins un. On dispose alors d'une fonction qui rend une sous-chaîne de la chaîne donnée, sous-chaîne spécifiée par l'indice de son premier caractère et un de plus que l'indice, dans la chaîne donnée, de son dernier caractère dans la chaîne donnée:
 
 

 
Exemples  
La fonction prem rend la chaîne de caractères qui ne comporte qu'un caractère, le premier de la chaîne donnée. Notons que cette spécification n'a de sens que si la chaîne donnée a, au moins, un caractère, c'est-à-dire si elle n'est pas vide:
 
 

 
L'implantation est simple, il suffit de considérer la sous-chaîne qui commence au premier caractère (i.e. celui d'indice 0) et qui se termine au second caractère (i.e. celui d'indice 1):
 
 

 
Considérons maintenant la fonction qui rend la chaîne de caractères obtenue en ôtant, à la chaîne donnée, son premier caractère:
 
 

 
Là encore l'implantation est facile, il suffit de remarquer que l'indice de fin est égal à la longueur de la chaîne:
 
 

 
On peut aussi avoir besoin du dernier caractère d'une chaîne donnée:
 
 

 
 

 
Enfin, considérons la fonction qui rend la chaîne de caractères obtenue en ôtant, à la chaîne donnée, son dernier caractère:
 
 

 
 

 
Comme dernier exemple, considérons la fonction permutation:  
 

 
 

 
Types Ligne et Paragraphe  
Les chaînes de caractères vues dans le paragraphe précédent peuvent comporter des caractères « fin de ligne ». Par exemple l'exécution de
 

rend  

 
 

 
Par la suite, nous considèrerons le type des chaînes de caractères qui ne comportent pas de caractères « fin de ligne » et nous nommerons « Ligne » le type de ces chaînes. Notons que le type « Ligne » possède donc toutes les fonctions du type « string ».
 
Un « Paragraphe » est alors une suite de lignes qui seront affichées les unes à la suite des autres, en passant à chaque fois à la ligne. Pour manipuler ces paragraphes, nous utiliserons les fonctions de base suivantes qui ont été ajoutées à la bibliothèque de DrScheme pour cet enseignement et se trouvent mentionnées dans la carte de référence:
 
 

 
Remarque  
Les fonctions paragraphe et lignes vérifient les propriétés suivantes:
 
Pour tout paragraphe para:
 
 

 
Pour toute liste de lignes L:
 
 

 
Exemple 1  
On voudrait écrire la définition d'une fonction qui, étant donnés deux paragraphes, les concatène c'est-à-dire rend le paragraphe qui contient les lignes du premier paragraphe puis les lignes du second paragraphe. Pour implanter cette fonction, on peut

• fabriquer, pour chacun des deux paragraphes, la liste de ses lignes (en utilisant la fonction lignes),
• concaténer ces deux listes (en utilisant la fonction append),
• fabriquer un paragraphe à partir de cette liste (en utilisant la fonction paragraphe):

 
 
 

 
Exemple 2  
On voudrait écrire la définition d'une fonction qui, étant donnée une ligne, affiche ses caractères « en triangle »: elle rend un paragraphe dont la première ligne est la ligne donnée, la deuxième ligne est la ligne donnée hormis le dernier caractère, la troisième ligne est la ligne donnée hormis les deux derniers caractères... Par exemple:
 

rend  

 
 

 
Sa spécification est donc:
 
 

 
Pour l'implantation de la fonction triangle1, remarquons que la première ligne du résultat est la ligne donnée et que les lignes suivantes sont égales à l'application de cette même fonction sur la ligne obtenue en supprimant le dernier caractère de la ligne donnée. On peut donc écrire la définition récursive suivante:
 
 

 
Exemple 3  
On voudrait maintenant avoir un triangle « dans l'autre sens »:
 

rend  

 
 

 
Sa spécification est donc:
 
 

 
L'implantation est un peu plus délicate. Faisons un dessin: (triangle2 "abcd") doit rendre le paragraphe  
 

 
la première ligne de ce paragraphe étant la donnée auquelle on a appliqué la fonction:  
 

 
et dans les lignes suivantes, on reconnait le résultat de l'application de la fonction à la ligne donnée hormis son premier caractère:  
 

 
mais en mettant un caractère espace devant chaque ligne:  
 

 
Ainsi, si l'on dispose d'une fonction ajout-prefixe de spécification
 
 

 
la fonction triangle2 peut être définie par:
 
 

 
Reste à implanter ajout-prefixe. Rappelons sa spécification:
 
 

 
Comme il faut concaténer une chaîne devant chaque ligne du paragraphe, il suffit, à partir du paragraphe donné:

• d'extraire la liste de ses lignes (en utilisant la fonction lignes),
• de « maper » la fonction qui concatène le préfixe donné à chaque élément de cette liste,
• de reconstituer le paragraphe résultat (en utilisant la fonction paragraphe).

 
D'où la définition:
 
 

 
Mais, avec la définition précédente, pour calculer (triangle2 "abcd"), après avoir calculé (triangle2 "bcd") qui renvoie le paragraphe comportant les trois lignes bcd, cd et d, on transforme ce paragraphe en une liste de trois lignes puis on reconstitue un autre paragraphe de trois lignes; et comme pour calculer (triangle2 "bcd") on transforme un paragraphe de deux lignes en une liste de deux lignes et qu'ensuite on reconstitue un paragraphe de deux lignes... Le calcul passe donc son temps à reconstruire un paragraphe à partir d'une liste de lignes obtenue en décomposant un paragraphe.
 
Pour l'efficacité, on peut donner d'autres définitions qui évitent ces décompositions--recompositions. La définition suivante utilise une fonction auxiliaire qui a une variable de plus que la fonction triangle2, variable qui contient une chaîne de caractères qui préfixera toutes les lignes du paragraphe résultat:
 
 

 
Pour l'implantation de la fonction triangle2aux, il suffit de remarquer que la première ligne est obtenue en concaténant le préfixe donné et la ligne donnée et que les lignes suivantes sont obtenues en appliquant (récursivement) la fonction

• à un préfixe obtenu en ajoutant un caractère espace au préfixe donné,
• à une ligne obtenue en supprimant le premier caractère de la ligne donnée.

 
D'où la définition: