4

次の単純な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での経験から、同じようなことを2回書いていると、おそらく何か間違ったことをしていると思います。

純粋な関数または単調な関数のいずれかを取ることができる単一の関数inOrderを作成する方法はありますか？

4

2 に答える 2

11

で、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 ()
于 2010-04-01T01:34:47.630 に答える
7

ツリー構造のData.Traversableクラスまたはクラスの実装を検討することをお勧めします。Data.Foldableそれぞれが単一のメソッドの定義のみを必要とします。

特に、Data.Foldableクラスを実装すると、次の2つの関数を無料で入手できます。

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

また、リストタイプで使用するのに慣れている豊富な関数セット（、、、、 ...）も提供foldrします。concatMapany

次のいずれかの関数を実装するだけで、次のインスタンスを作成できますData.Foldable。

foldMap :: Monoid m => (a -> m) -> t a -> m
foldr :: (a -> b -> b) -> b -> t a -> b
于 2010-04-01T01:54:35.707 に答える