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

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

4 голосов
/ 01 апреля 2010

Учитывая следующее простое определение 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

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

Можно ли как-нибудь написать одну функцию вOrder, которая может принимать чистые или монадические функции?

Ответы [ 2 ]

11 голосов
/ 01 апреля 2010

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

mapM_ print $ inOrder tree

Просто чтобы напомнить типы функций, которые я упомянул: 

mapM :: (Monad m) => (a -> m b) -> [a] -> m [b]
mapM_ :: (Monad m) => (a -> m b) -> [a] -> m ()
7 голосов
/ 01 апреля 2010

Возможно, вы захотите взглянуть на реализацию класса 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
...