Problématique des listes Haskell

1 pièce(s) jointe(s)

Bonjour,

Pour quelle raison, à la ligne no 2 du code ci-dessous, suis-je obligé de mettre le "t" à droite du signe égal entre crochets ?
Code:

1 2 3 dernier [] = [] dernier [t] = [t] dernier (x:xs) = dernier xs
Pièce jointe 245883

Merci pour votre aide.

J'ai peut-être une piste.

En modifiant le code ainsi je réussis à ne pas mettre de crochets...
Code:

1 2 3 dernier [] = error "erreur" dernier [t] = t dernier (x:xs) = dernier xs
Mais je souhaiterais comprendre la raison.

avec l'exemple d'une liste [10,20,30] est-ce que le déroulement ci-dessous est bien juste ?

dernier [10,20,30] = dernier [20,30]
dernier [20,30] = dernier [30]
dernier [30] = 30 ou alors dernier [30] = [].... ?

La réponse vient naturellement si tu cherches de quel type ta fonction "dernier" est. Dans ton premier code :
Code:

1 2 3 dernier [] = [] dernier [t] = [t] dernier (x:xs) = dernier xs
La première ligne indique que l'image d'une liste vide est une liste vide, ce qui veut dire que dernier est du type "[a] -> [b]" : il prend un paramètre de type liste d'élément de type a et renvoie une liste (et comme la liste est vide, le contenu pourrait être de n'importe quel type a priori).

Néanmoins cela signifie que pour ta deuxième ligne, dernier ne peut pas être d'un type incompatible, si la liste a un seul élément "t", tu souhaiterais probablement que la fonction renvoie "t" (puisque c'est le seul, et donc le dernier, élément de ta liste) mais cela signifierais que dernier serait du type "[a] -> a" et qu'il ne renverrait pas une liste... Une fonction ne peut avoir qu'un seul type, donc ceci est impossible. Il faut alors que ta fonction renvoie une liste et le choix fait a été de renvoyer une liste contenant seulement l'élément "t", autrement dit "[t]". dernier est maintenant fixé du type "[a] -> [a]" et est une fonction qui renvoie une liste contenant le dernier élément de son argument s'il existe ou une liste vide sinon, c'est un choix qui se défend et qui a l'avantage de ne jamais planter. Une alternative dans le même esprit serait d'utiliser le type "Maybe a" qui peut contenir une valeur du type a "Just a" ou aucune valeur "Nothing" :
Code:

1 2 3 4 dernier :: [a] -> Maybe a dernier [] = Nothing -- si la liste est vide, renvoie "Nothing" dernier [x] = Just x -- si la liste contient un seul élément, c'est le dernier, renvoie "Just" cet élément dernier (_:xs) = dernier xs -- si la liste a plus d'un élément, le dernier élément est le dernier élément de la queue de la liste
Avantage : "Maybe a" indique clairement que le résultat est soit une seule valeur (le dernier élément), soit aucune (si la liste est vide). Avec [a] le doute plane sur le fait que ta fonction puisse renvoyer plusieurs valeurs.
Désavantage : Très souvent cette fonction sera utilisé dans un contexte ou l'on voudrait concaténer le dernier élément d'une liste au bout d'une autre (ou au milieu d'une autre), dans ce cas la première version serait légèrement plus pratique.
Conclusion : Franchement la version avec Maybe est plus claire et le coût n'est pas bien lourd si l'on sait utiliser les fonctions de la librairie Data.Maybe.

Ta deuxième version :
Code:

1 2 3 dernier [] = error "erreur" dernier [t] = t dernier (x:xs) = dernier xs
Maintenant ta fonction a bien le type "[a] -> a" ... Seul problème, vu que le type "a" est quelconque, ta fonction ne peut pas créer d'élément de ce type, dans le cas d'une liste vide ta seule option est donc de planter. Ta fonction est "partielle", c'est-à-dire qu'elle ne fonctionne pas correctement pour toutes les entrées possibles vu son type. Ceci est une source de problème potentiels (tout programmeur Haskell qui les as utilisé a un jour été confronté à un bug résultant de l'usage d'un "head" ou "last" sur une liste vide) et est donc assez mal considéré par la communauté Haskell actuelle puisque celle ci est généralement très attachée à la robustesse apporté par le typage statique et le système de type riche. Néanmoins ces fonctions ont parfois leurs usages et théoriquement il est tout à fait légitime d'utiliser cette fonction à une position où tu es certain que la liste passée est non-vide (parce que tu viens de la créer ou parce que tu as déjà traité le cas où elle était vide), en pratique tu auras vraisemblablement des problèmes tôt ou tard avec ce type de fonction qui t'amèneront à apprécier la philosophie actuelle de la communauté Haskell (tout simplement, comme le compilateur ne vérifie pas que ton raisonnement reste valable, il y aura des cas où des modifications ultérieures du code autour de ton usage de "dernier" entraineront un appel à cette fonction sur une liste vide... avec un peu de chance et de test ce bug se révèlera avant que tu n'envoies ton code en production...).

Bien sûr durant le processus d'apprentissage toute ces options sont intéressantes, il faut juste avoir conscience des faiblesses de certaines approches.
--
Jedaï