How to decorate a Tree in Haskell

Question

I want to tag each element of a tree with a different value (Int, for example sake). I managed to do this but the code is ugly as a beast and I don't know how to work with Monads yet.

My take:

data Tree a = Tree (a, [Tree a])

tag (Tree (x, l)) n = ((m, x), l')
 where (m,l') = foldl g (n,[]) l
        where g (n,r) x = let ff = tag x n in ((fst $ fst ff) +1, (Tree ff):r)

Do you know some better way?

EDIT: I just realized that the above foldl really is mapAccumL. So, here is a cleaned version of the above:

import Data.List (mapAccumL)

data Tree a = Tree (a, [Tree a])

tag (Tree (x, l)) n = ((m,x),l')
  where (m,l') = mapAccumL g n l
        g n x  = let ff@((f,_),_) = tag x n in (f+1,ff)

Answer 1

Taking advantage of Data.Traversable and some useful GHC extensions, we can refactor sacundim's solution further:

{-# LANGUAGE DeriveFunctor, DeriveFoldable, DeriveTraversable #-}

import Control.Monad.State
import Data.Foldable
import Data.Traversable

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

postIncrement :: Enum s => State s s
postIncrement = do val <- get
                   put (succ val)
                   return val

-- Works for any Traversable, not just trees!
tag :: (Enum s, Traversable t) => s -> t a -> t (a, s)
tag init tree = evalState (traverse step tree) init
    where step a = do tag <- postIncrement
                      return (a, tag)