Монады и пользовательские функции обхода в Haskell

Question

Учитывая следующее простое определение BST:

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 

Я хотел бы написать функцию в заказ, который может иметь побочные эффекты. Я добился того, что с:

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 

Это прекрасно работает, но это, кажется, повторяющаяся - та же логика уже присутствует в заказовМои и мой опыт работы с Haskell заставляет меня верить, что я, вероятно, делать что-то неправильно, если я Я пишу аналогичную вещь дважды.

Есть ли способ, которым я могу написать одну функцию inOrder, которая может принимать либо чистые, либо монадические функции?

Answer 1

В inOrder вы сопоставляете Tree x с номером [x], i. е. вы секвенируете свое дерево. Почему бы просто не использовать mapM или mapM_ в результирующем списке?

mapM_ print $ inOrder tree 

Напомним типы функций, которые я упомянул:

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

Answer 2

Вы можете посмотреть на реализацию класса Data.Traversable класса или Data.Foldable для структуры дерева. Каждому требуется только определение одного метода.

В частности, если вы реализуете Data.Foldable класса, вы получаете следующие две функции бесплатно:

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

Это также даст вам богатый набор функций (foldr, concatMap, any ...), которые вы используете для использования с типом списка.

Вы только должны выполнить одну из следующих функций для создания экземпляра из Data.Foldable:

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