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