Commençons par corriger les petites erreurs d'étourderie (genre tu as oublié un "=" après le otherwise dans la dernière garde de tmRemove, tu as mis "Empty_" au lieu de "Empty _", tu as utilisé "just" au lieu de "Just"...), on a ça :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
| -- Definition d'un arbre binaire
data TreeMap b = Empty | Node Int b (TreeMap b) (TreeMap b)
-- Types des fonctions :
tmLookup :: TreeMap Int -> b -> Maybe b -- rechercher la valeur associee a une cle passee en parametre
tmInsert :: TreeMap b -> Int -> b -> TreeMap b -- ajouter une entree dans la table
tmRemove :: TreeMap b -> Int -> TreeMap b -- enlever une entree dont la clef est passee en parametre
-- Code
tmLookup (Node k v left right) k'
| k' == k = Just v
| k' < k = tmLookup (left) k' -- recursion dans le sous arbre gauche
| otherwise = tmLookup (right) k' -- recursion dans le sous arbre droit
tmInsert Empty k' v' = Node k' v' Empty Empty -- Si arbre (ou sous arbre) vide
tmInsert (Node k v l r) k' v'
| k' == k = Node k' v' l r
| k'<k = Node k v (tmInsert l k' v')r
| otherwise = Node k v l (tmInsert r k' v')
tmMerge :: TreeMap b -> TreeMap b -> TreeMap b
tmMerge Empty t = t
tmMerge (Node k v l r) t = Node k v l (tmMerge r t)
tmRemove Empty _ = Empty
tmRemove (Node k v l r) k'
| k'<k = Node k v (tmRemove l k') r
| k'>k = Node k v l (tmRemove r k')
| otherwise = tmMerge l r |
Ensuite ce code a toujours des problèmes, en particulier, le type de tmLookup est faux et semble trahir une confusion sur ce qu'elle doit faire :
tmLookup :: TreeMap Int -> b -> Maybe b
je suggère que le type devrait plutôt être :
tmLookup :: TreeMap b -> Int -> Maybe b
Comme l'inférence de type te le dirais si tu retirais la déclaration de type (le corps de la fonction apparait correct).
Dernièrement la fonction tmMerge ne préserve pas la structure d'arbre de recherche que les autres fonctions utilisent, ce qui suggère qu'elle est erronée, ou plus exactement, qu'elle devrait être locale à tmRemove, et non une fonction du top-level (surtout si tu ne dis rien sur les propriétés nécessaires de l et r pour avoir un résultat correct).
--
Jedaï
Partager