IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Haskell Discussion :

Problématique des listes Haskell


Sujet :

Haskell

  1. #1
    Futur Membre du Club
    Homme Profil pro
    Ingénieur après-vente
    Inscrit en
    novembre 2014
    Messages
    366
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Suisse

    Informations professionnelles :
    Activité : Ingénieur après-vente

    Informations forums :
    Inscription : novembre 2014
    Messages : 366
    Points : 9
    Points
    9
    Par défaut Problématique des listes Haskell
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    dernier [] = []
    dernier [t] = [t]
    dernier (x:xs) = dernier xs
    Nom : crochets.JPG
Affichages : 432
Taille : 82,6 Ko

    Merci pour votre aide.

  2. #2
    Futur Membre du Club
    Homme Profil pro
    Ingénieur après-vente
    Inscrit en
    novembre 2014
    Messages
    366
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Suisse

    Informations professionnelles :
    Activité : Ingénieur après-vente

    Informations forums :
    Inscription : novembre 2014
    Messages : 366
    Points : 9
    Points
    9
    Par défaut
    J'ai peut-être une piste.

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

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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] = [].... ?

  3. #3
    Expert éminent
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    avril 2003
    Messages
    6 245
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : avril 2003
    Messages : 6 245
    Points : 8 560
    Points
    8 560
    Par défaut
    La réponse vient naturellement si tu cherches de quel type ta fonction "dernier" est. Dans ton premier code :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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 Haskell : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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ï

Discussions similaires

  1. Représentation intervallaire des listes arborescentes
    Par PMAR dans le forum Décisions SGBD
    Réponses: 1
    Dernier message: 05/11/2004, 10h35
  2. [servlet] gestion des listes d'erreurs ?
    Par MatMeuh dans le forum Servlets/JSP
    Réponses: 8
    Dernier message: 27/10/2004, 11h19
  3. [html:text][indexed]Valeurs des liste null...
    Par thibaut dans le forum Servlets/JSP
    Réponses: 13
    Dernier message: 08/09/2004, 10h36
  4. [glut] de l'intérêt des listes
    Par khayyam90 dans le forum OpenGL
    Réponses: 3
    Dernier message: 26/07/2004, 11h35
  5. [langage] probleme avec les listes dans des listes
    Par pqmoltonel dans le forum Langage
    Réponses: 7
    Dernier message: 27/04/2004, 13h32

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo