Haskell二叉树函数(图)

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),它会使代码对其他代码更具可读性.

Answer 2

我会假装这是家庭作业而不是放弃所有的答案.如果我弄错了,我道歉.

可能你的Tree类型看起来像这样:

data Tree a = TreeNode a (Tree a) (Tree a) | EmptyNode

这里有两种情况,您需要mapT为每种情况编写一个实现:

• 一个内部节点,TreeNode它带有一个类型的值,a并且有一个左子项和右子项.在这种情况下需要做什么？
• 终端节点EmptyNode.在这种情况下需要做什么？