Monades et fonctions traversal personnalisés dans Haskell

Question

Compte tenu de la définition simple de BST suivante:

data Tree x = Empty | Leaf x | Node x (Tree x) (Tree x) 
      deriving (Show, Eq) 

inOrder :: Tree x -> [x] 
inOrder Empty     = [] 
inOrder (Leaf x)    = [x] 
inOrder (Node root left right) = inOrder left ++ [root] ++ inOrder right 

Je voudrais écrire une fonction dans l'ordre qui peuvent avoir des effets secondaires. J'ai réalisé que, avec:

inOrderM :: (Show x, Monad m) => (x -> m a) -> Tree x -> m() 
inOrderM f (Empty) = return() 
inOrderM f (Leaf y) = f y >> return() 
inOrderM f (Node root left right) = inOrderM f left >> f root >> inOrderM f right 

-- print tree in order to stdout 
inOrderM print tree 

Cela fonctionne bien, mais il semble répétitif - la même logique est déjà présent dans afinde et mon expérience avec Haskell me porte à croire que je fais sans doute quelque chose de mal si je J'écris une chose similaire deux fois.

Y a-t-il un moyen pour que je puisse écrire une seule fonction dans InOrder qui peut prendre des fonctions pures ou monadiques?

Answer 1

Dans inOrder vous mappez un Tree x à un [x], i. e. vous séquenciez votre arbre. Pourquoi ne pas simplement utiliser mapM ou mapM_ dans la liste qui en résulte?

mapM_ print $ inOrder tree 

Juste pour rappeler les types de fonctions que je l'ai mentionné:

mapM :: (Monad m) => (a -> m b) -> [a] -> m [b] 
mapM_ :: (Monad m) => (a -> m b) -> [a] -> m() 

Answer 2

Vous pourriez vouloir regarder la mise en œuvre de la classe de classe Data.Traversable ou Data.Foldable pour votre structure arborescente. Chacun ne nécessite que la définition d'une seule méthode.

En particulier, si vous implémentez la classe Data.Foldable, vous obtenez les deux fonctions suivantes gratuitement:

mapM_ :: (Foldable t, Monad m) => (a -> m b) -> t a -> m() 
toList :: Foldable t => t a -> [a] 

Il vous donnera également l'ensemble des fonctions riches (foldr, concatMap, any, ...) que vous avez l'habitude d'utiliser avec le type de liste.

Vous ne devez mettre en œuvre l'une des fonctions suivantes pour créer une instance de Data.Foldable:

foldMap :: Monoid m => (a -> m) -> t a -> m 
foldr :: (a -> b -> b) -> b -> t a -> b