Haskell / Level-order tree traversal with foldr-CodePudding

There is a data type Tree, which describes my 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)

The task is: implement in-order, pre-order, post-order and level-order tree traversals with foldr. I have implemented all of them but level-order traverse is not efficient much. How can I improve it to make it faster but still with foldr?

The code:

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]))

CodePudding user response：

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))