Define a Map for Tree data in Haskell

Question

I have the a Tree data structure like this:

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

Is it possible to write a higher-order function traverse with the following declaration which just traverses (or whatever) the tree and reconstructs it?

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

Please note the traverses signature. It doesn't get a list of Tree. It only accepts one node at a time.

I think the signature needs to change to accept lists in order to do this. Like this:

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)

Note your function has the same signature as fmap so you should implement Functor for your type:

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

in fact you can have the compiler generate your functor instance for you:

{-# LANGUAGE DeriveFunctor #-}

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