我如何定义一个 Haskell 函数,将函数应用于二叉树中的每个值?所以我知道它类似于 map
函数 - 它的类型是:
mapT :: (a -> b) -> Tree a -> Tree b
但仅此而已......
最佳答案
您可以声明类 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
的通常行为),它会使代码对其他人更具可读性。
关于algorithm - Haskell 二叉树函数( map ),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2756621/