J'ai cette fonction pour obtenir la valeur minimale de mon BST, tapez Int:
maxBST :: (Ord t) => BST t -> t maxBST Nil = //? maxBST (Node left value right) = max (maxBST left) (max value (maxBST right))
Maintenant, je veux refaire cette fonction afin qu'elle fonctionne également pour le BST paramétré, comme ceci:
maxBST :: BST Int -> Int maxBST Nil = -1000000 maxBST (Node left value right) = max (maxBST left) (max value (maxBST right))
Le problème ici est de trouver le bon //? value, de sorte qu'elle soit minimale pour le type t . Avez-vous une suggestion à ce sujet?
3 Réponses :
Don't goto nil, juste déstructurer à gauche et à droite et voir si les deux sont nuls et gérer les cas
maxBST Nil = error "your function shouldn't reach here" maxBST (Node Nil value Nil) = value maxBST (Node left@(Node _ _ _) value Nil) = max (maxBST left) value maxBST (Node Nil value right@(Node _ _ _)) = max value (maxBST right)
Le problème fondamental ici est que votre signature de type (comme celle de maximum ) est un mensonge. Vous ne pouvez pas garantir de produire l'élément maximal à partir d'une structure de données qui ne peut contenir aucun élément. Une valeur sentinelle spéciale peut couvrir ce problème dans certains cas, mais même dans ces cas, elle s'effondre si vous regardez attentivement. Quel est l'élément minimum de Node Nil -2000000 Nil ? Il s'agit d'un arbre non vide, vous devriez donc pouvoir obtenir son maximum, mais votre implémentation renvoie -1000000 à la place, comme si l'arbre était vide!
Une chose que vous pourriez essayer qui ferait un meilleur travail pour balayer le problème sous le tapis serait d'ajouter une contrainte Bounded, de sorte que vous puissiez utiliser minBound comme élément "neutre". Alors au moins, vous n'obtenez pas de résultats erronés comme dans mon exemple, mais vous ne pouvez toujours pas distinguer un arbre vide d'un arbre ne contenant que le minimum.
Mieux vaut ajuster votre signature de type pour dire la vérité. Vous pouvez renvoyer Maybe t au lieu de juste t , en utilisant Nothing pour indiquer "désolé, cet arbre était vide". En ce qui concerne l'implémentation, vous pouvez juste la chose évidente de la force brute de la correspondance de modèles sur les appels récursifs - c'est maladroit, mais cela fonctionne.
Mieux encore, cependant, serait d'implémenter Foldable pour votre type d'arbre (une bonne idée dans tous les cas), afin que vous puissiez profiter de sa toList . En supposant que vous l'ayez fait, cette fonction maximale devient facile:
maxBST t = case toList t of [] -> Nothing xs -> Just $ maximum xs
user: pigworker a une bonne réponse à ce problème, avec foldMap sur un type IIRC étendu. Je vais essayer de trouver le lien ... le voici - bien que ce soit un problème différent, bien que lié.
Je suis d'accord avec la réponse de @ amalloy, que renvoyer un type Maybe est la meilleure approche ici.
Cependant, il existe une autre approche si vous êtes déterminé à toujours renvoyer une «valeur réelle» et que ce soit un «minimum» raisonnable pour le type. Et c'est pour modifier la signature de type afin que les éléments de l'arbre doivent être d'un type qui est une instance de Bounded ainsi que Ord . Ce serait:
maxBST :: (Ord t, Bounded t) => BST t -> t maxBST Nil = minBound maxBST (Node left value right) = max (maxBST left) (max value (maxBST right))
Notez que, bien que cela fonctionne sur Int , il ne sera pas identique à votre fonction d'origine, car le minBound pour Int est bien inférieur à -1000000.
J'ai mentionné cette option dans ma réponse, et vous manquez la mise en garde importante que j'ai incluse: il est impossible de faire la différence entre un arbre vide et un arbre contenant uniquement la valeur minBound .
Cela n'affecte pas la réponse à votre question, mais s'il s'agit vraiment d'un arbre de recherche binaire, vous ne devriez pas avoir besoin de parcourir le tout pour trouver où se trouve l'élément maximal.