單子和自定義遍歷函數在Haskell

考慮下面這個簡單的BST定義：單子和自定義遍歷函數在Haskell

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，它可以使用純函數或單函數？

來源

2010-04-01 Bill

在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-01 01:34:47

這可能是有益的認識到，mapM_ f是隻是sequence_簡寫。地圖f - 也就是說，你*可以*使用普通的地圖向每個inOrder項目應用一個函數（a - > m b）。現在你有一個monadic動作列表，但它們沒有順序。函數sequence_接着將它們接受，並且將它們按順序應用於它們，從而給出按照列表順序進行單向操作的操作。當然，優化的神奇意味着這個列表很可能永遠不會被建立或一次完成！ – MtnViewMark 2010-04-01 02:31:45

mapM是相似的，但使用序列，並且序列與sequence_相同，只是它收集結果，因爲它運行monadic操作並使該集合成爲複合操作的結果。 – MtnViewMark 2010-04-01 02:32:25

你可能想看看在實施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

來源

2010-04-01 01:54:35

+1我在列表上的'mapM_'不夠一般:) – 2010-04-01 01:56:49

單子和自定義遍歷函數在Haskell

回答

相關問題