Discussion :

[Fused]

Salut, encore des soucis pour pondre du bon haskell !

Je programme un arbre binaire, j'ai des erreurs, dont un "Syntax error in declaration (unexpected `}', possibly due to bad layout)" dont je n'arrive pas a me defaire (dans les deux dernieres fonctions).

Que pensez vous de la definition des fonctions de base ?
Voyez vous ou sont mes erreurs ?

Merci beaucoup d'avance pour votre aide.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[Jedai]

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 :

Code Haskell :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

tmLookup :: TreeMap Int -> b -> Maybe b

je suggère que le type devrait plutôt être :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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ï