有人可以幫助我定義一個函式 minTree，它使用 foldr 在二叉樹中找到具有最小值的節點。我開始了一些事情，但我不知道如何在我的代碼中使用 foldr：
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...
我被困在如何定義 foldr 以回傳最小節點
uj5u.com熱心網友回復：
一個可能的解決方案如下：
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)
的Foldable實體實作Tree是后序遍歷（右-左-根），這是代碼的主要部分。 minMaybe使用內置函式可能可以避免，但我保持它的表現力，所以主要部分仍然清晰。
作為@ammalloy指出，我們可以擺脫minMaybe和利用coerce，foldMap以及Min半群。老實說，我不知道它是如何coerce作業的，但是foldMap將一個函式應用于包裝在一個資料型別中的資料，Foldable并使用它們的Monoidaloperation聚合結果<>，這就是Min這里使用的原因。
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)
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/350110.html
標籤：哈斯克尔
上一篇：通用型別（地圖。過濾器）