haskell - 如何在 Haskell 中装饰一棵树

Question

我想用不同的值(例如，Int)标记树的每个元素。我设法做到了，但代码丑得像野兽，我还不知道如何使用 Monads。

我的看法:

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)

你知道更好的方法吗？

编辑:
我才意识到上面的 foldl 真的是 mapAccumL。所以，这里是上面的一个干净的版本:

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

利用 Data.Traversable和一些有用的 GHC 扩展，我们可以重构 sacundim's solution更远:

{-# 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)