Making a foldl function for BinarySearchTree-CodePudding

I've made a foldr function for BinSearchTree, but I'm not quite sure if it's correct. Do any of you see a problem here? Any tips? (I can't use deriving Foldable)

data BinSearchTree a
  = Empty
  | Branch (BinSearchTree a) a (BinSearchTree a)
  deriving (Eq, Show)


instance Foldable BinSearchTree where 
  foldr f x Empty = x
  foldr f x (Branch left a right) = f a (foldr f y right)
         where y = foldr f x left

CodePudding user response：

You fold the left subtree first here

y = foldr f x left

then you fold right subtree with left result as an accum

foldr f y right

and only after you fold a branch's argument

f a folding_result

To implement right fold you need to start from folding right subtree, then call a function on a branch's argument, and only then fold the left one

foldr f (f a (foldr f x right)) left