algorithm - Haskell 二叉树函数( map )

Question

我如何定义一个 Haskell 函数，将函数应用于二叉树中的每个值？所以我知道它类似于 map 函数 - 它的类型是:

mapT :: (a -> b) -> Tree a -> Tree b

但仅此而已......

Answer 1

您可以声明类 Functor 的实例。这是允许映射函数的数据类型的标准类。请注意 fmap 的类型与您的 mapT 的类型有多相似:

class Functor f where
  fmap :: (a -> b) -> f a -> f b

假设您的树定义为

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

然后你可以这样声明一个Functor的实例:

instance Functor Tree where
  fmap f (Node l r) = Node (fmap f l) (fmap f r)
  fmap f (Leaf x) = Leaf (f x)

这是你如何使用它:

main = do
  let t = Node (Node (Leaf 1) (Leaf 2)) (Leaf 3)
  let f = show . (2^)
  putStrLn $ "Old Tree: " ++ (show t)
  putStrLn $ "New Tree: " ++ (show . fmap f $ t)

输出:

Old Tree: Node (Node (Leaf 1) (Leaf 2)) (Leaf 3)
New Tree: Node (Node (Leaf "2") (Leaf "4")) (Leaf "8")

为了方便也可以定义:

mapT = fmap

当然，您可以在没有类型类的情况下做到这一点，但如果您使用标准函数(每个人都知道 fmap 的通常行为)，它会使代码对其他人更具可读性。