Haskell树木地图

Question

data Tree a = Empty | Node a (Tree a) (Tree a)

map :: (a -> b) -> [a] -> [b]

如何定义一个像map一样运行但在树上工作的函数？新功能的typeignature将是:

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

是否可以为地图创建通用类型类？

Answer 1

Prepec中已存在该类型类:Functor.

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

要实现它,您可以使用DeriveFunctor语言扩展,以便GHC只需一个deriving子句即可为您实现:

{-# LANGUAGE DeriveFunctor #-}

data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Functor)

mapTree :: (a -> b) -> Tree a -> Tree b
mapTree = fmap

或者您可以手动实现它:

data Tree a = Empty | Node a (Tree a) (Tree a)

mapTree :: (a -> b) -> Tree a -> Tree b
mapTree _ Empty = Empty
mapTree f (Node x l r) = Node (f x) (mapTree f l) (mapTree f r)

instance Functor Tree where
    fmap = mapTree