有一個資料型別Tree，它描述了我的樹：
data Tree a = Leaf | Node (Tree a) a (Tree a) deriving (Eq, Show)
newtype Preorder a = PreO (Tree a) deriving (Eq, Show)
newtype Postorder a = PostO (Tree a) deriving (Eq, Show)
newtype Levelorder a = LevelO (Tree a) deriving (Eq, Show)
任務是：用 實作、in-order和pre-order樹遍歷。我已經實作了所有這些，但遍歷效率不高。我該如何改進它以使其更快但仍然使用？post-orderlevel-orderfoldrlevel-orderfoldr
編碼：
instance Foldable Tree where
foldr f ini Leaf = ini
foldr f ini (Node left num right) = foldr f (f num (foldr f ini right)) left
instance Foldable Preorder where
foldr f ini (PreO Leaf) = ini
foldr f ini (PreO (Node left num right)) = f num (foldr f (foldr f ini (PreO right)) (PreO left))
instance Foldable Postorder where
foldr f ini (PostO Leaf) = ini
foldr f ini (PostO (Node left num right)) = foldr f (foldr f (f num ini) (PostO right)) (PostO left)
instance Foldable Levelorder where
foldr f ini (LevelO Leaf) = ini
foldr f ini (LevelO tree@(Node left num right)) = helper [tree]
where
helper [] = ini
helper (Leaf : xs) = helper xs
helper ((Node left num right) : xs) = f num (helper (xs [left, right]))
uj5u.com熱心網友回復：
instance Foldable Levelorder where
foldr f ini (LevelO Nil) = ini
foldr f ini (LevelO tree@(Branch left num right)) = helper [tree] []
where
helper [] rest
| null rest = ini
| otherwise = helper (reverse rest) []
helper (Nil : xs) rest = helper xs rest
helper ((Branch left num right) : xs) rest = f num (helper xs (right:left:rest))
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/517133.html
標籤：哈斯克尔树
上一篇：脫糖Do-Notation函式