find the node with minimal value in binary tree with foldr-CodePudding

Someone can help me to define a function minTree, that find the node with minimum value in a binary tree using foldr. I start something, but I don't know how to use foldr within my code:

data Tree a 
    = Leaf
    | Node (Tree a) a (Tree a)
    deriving (Show, Eq)

  minTree :: (Ord a) => Tree a -> Maybe a
  minTree Leaf = Nothing
  minTree (Node Leaf a _) = Just a
  minTree (Node left a _) = minTree left
  minTree = foldr...

I am stuck on how define foldr to return the minimum Node

CodePudding user response：

A possible solution is as follows:

data Tree a 
    = Leaf
    | Node (Tree a) a (Tree a)
    deriving (Show, Eq)

instance Foldable Tree where
  foldr f ini Leaf = ini
  foldr f ini (Node left x right) = f x $ foldr f (foldr f ini right) left

minTree :: (Ord a) => Tree a -> Maybe a
minTree tree = foldr minMaybe Nothing tree

minMaybe :: (Ord a) => a -> Maybe a -> Maybe a
minMaybe x Nothing = Just x
minMaybe x (Just y) = Just (min x y)

The Foldable instance implementation for Tree is post-order traversal (right-left-root), which is the main part of the code. minMaybe can probably be avoided using built-in functions, but I kept it expressive so the main part remains clear.

As @ammalloy has pointed out, we can get rid of minMaybe and make use of coerce, foldMap, and the Min Semigroup. Honestly, I don't know how coerce works but foldMap applies a function to the data wrapped in a data type with a Foldable instance and aggregates the results using their Monoidal operation <>, which is why Min is used here.

data Tree a 
    = Leaf
    | Node (Tree a) a (Tree a)
    deriving (Show, Eq)

instance Foldable Tree where
  foldr f ini Leaf = ini
  foldr f ini (Node left x right) = f x $ foldr f (foldr f ini right) left

minTree :: (Ord a) => Tree a -> Maybe a
minTree = coerce . foldMap (Just . Min)