在Haskell中为树数据定义Map

Question

我有这样的Tree数据结构:

data Tree a = ATree a [Tree a] 
            deriving Show

是否有可能traverse使用以下声明编写一个更高阶的函数,该声明只是遍历(或者不管)树并重构它？

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

请注意traverse签名.它没有得到树的列表.它一次只接受一个节点.

我认为签名需要更改为接受列表才能执行此操作.像这样:

traverse :: (a -> b) -> [Tree a] -> [Tree b]

Answer 1

traverse :: (a -> b) -> Tree a -> Tree b
traverse f (ATree e l) = ATree (f e) (map (traverse f) l)

请注意,您的函数具有相同的签名,fmap因此您应该Functor为您的类型实现:

instance Functor Tree where
    fmap f (ATree e l) = ATree (f e) (fmap (traverse f) l)

实际上,您可以让编译器为您生成functor实例:

{-# LANGUAGE DeriveFunctor #-}

data Tree a = ATree a [Tree a] deriving (Show, Functor)