本文介绍了如何在Haskell中装饰一棵树的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述 29岁程序员，3月因学历无情被辞！ 我想用一个不同的值来标记树的每个元素（例如，int）。我设法做到了这一点，但代码很丑陋，我不知道如何使用Monads。 我的看法： 数据树a =树（a，[Tree a]） 标签（Tree（x，l））n = （m，x），l'）其中（m，l'）= foldl g（n，[]）l 其中g（n，r）x = let ff = （（fst $ fst ff）+1，（Tree ff）：r） 更好的方法？ 编辑： 我刚才意识到上面的foldl真的是mapAccumL。所以，这里是上面的清理版本： import Data.List（mapAccumL） 数据树a =树（a，[树a]） 标签（树（x，l））n =（（m，x），l'）其中（m， （f + 1，ff） gnx = let ff @ p> 解决方案我稍微修改了您的类型。仔细研究这段代码： import Control.Monad.State - 最好不要使用一对作为构造函数的参数数据树a =树a [树a]派生显示 - 我们通常希望最后使用树参数;它使更容易组成树函数。 - - 另外，Enum类是你想要的而不是数字; - 您想要给我下一个标记操作，这是Enum的succ - 方法。 （对于Int，succ是（+1）。） tag :: Enum t => t - >树a - >树（a，t）标签init tree = - tagStep是动作发生的地方。这只是让球 - 滚动。 evalState（tagStep tree）init - 这是计算的一个单子步骤。它假定 - 它可以隐式地访问当前标签值。我会 - 在评论中注释它。 tagStep :: Enum t =>树a - >状态t（树（a，t）） tagStep（树a子树）= do - 首先，递归到子树中。 mapM是一个实用函数 - 用于在 - 元素列表上执行一个monadic动作（如tagStep），并生成结果列表。 子树'< - mapM tagStep子树 - 单态动作get访问State monad中的隐式状态参数 - 。变量标签获取值。 标签< - get - monadic动作put将隐式状态参数设置为 - State monad。下一个get会看到succ标签的值 - （假设没有其他放入）。 - - 请注意，当我们在上面执行mapM tagStep子树时，这将为 - 为每个子树执行get和put（succ标记）。 put（succ tag） return $树（a，tag）子树' 编辑：与上述方法相同，但将一轮重构转换为可重复使用的部分： - 这个函数不是解决方案的一部分，但它可以帮助您 - 了解下面的mapTreeM。 mapTree ::（a - > b） - >树a - >树b mapTree fn（Tree a subtrees）= 让子树'= map（mapTree fn）子树 a'= fn a 树a'子树' - 通常你会这样写这个函数： mapTree'fn（Tree a subtrees）= Tree（fn a）$ map（mapTree'fn）子树 - 但是我写了很长一段时间来展示与 - following的相似性，它从提取tagStep定义的结构 - 上面的第一个解决方案。 mapTreeM :: Monad m => （a - > m b） - >树a - > m（Tree b） mapTreeM action（Tree a subtrees）= do subtrees'< - mapM（mapTreeM action）subtrees a' return $树'子树' - 整个业务中获取状态并将后续元素 - in作为替换可以被抽象出来。这个动作就像一个 - 增量后的运算符。 postIncrement :: Enum s =>状态s postIncrement = do val 放（succ val）返回val - 现在可以很容易地根据这些标记来编写标记。 标记init tree = evalState（mapTreeM步骤树）init 其中step a = do标记< - postIncrement return（a，tag） 如果需要，可以使 mapTreeM 在子树之前处理本地值： mapTreeM action（Tree a subtrees）= 做'< - 动作a 子树'< - mapM （mapTreeM action）子树返回$ Tree a'子树' 使用 Control.Monad 你可以把它变成一行： mapTreeM action Tree a subtrees）= - 将树构造器应用于两个动作的结果 liftM2树（动作a）（mapM（mapTreeM动作）子树） - mapTreeM'action（Tree a subtrees）= liftM2（flip Tree）（mapM（mapTreeM action）subtrees）（action a） 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) 解决方案 I've modified your types slightly. Study this code carefully:import Control.Monad.State-- It's better not to use a pair as the argument of the constructordata Tree a = Tree a [Tree a] deriving Show-- We typically want to put the Tree argument last; it makes it-- easier to compose tree functions.---- Also, the Enum class is what you want here instead of numbers;-- you want a "give me the next tag" operation, which is the succ-- method from Enum. (For Int, succ is (+1).)tag :: Enum t => t -> Tree a -> Tree (a, t)tag init tree = -- tagStep is where the action happens. This just gets the ball -- rolling. evalState (tagStep tree) init-- This is one monadic "step" of the calculation. It assumes that-- it has access to the current tag value implicitcly. I'll-- annotate it in the comments.tagStep :: Enum t => Tree a -> State t (Tree (a, t))tagStep (Tree a subtrees) = do -- First, recurse into the subtrees. mapM is a utility function -- for executing a monadic action (like tagStep) on a list of -- elements, and producing the list of results. subtrees' <- mapM tagStep subtrees -- The monadic action "get" accesses the implicit state parameter -- in the State monad. The variable tag gets the value. tag <- get -- The monadic action `put` sets the implicit state parameter in -- the State monad. The next get will see the value of succ tag -- (assuming no other puts in between). -- -- Note that when we did mapM tagStep subtrees above, this will -- have executed a get and a put (succ tag) for each subtree. put (succ tag) return $ Tree (a, tag) subtrees'EDIT: Same solution as above, but put through one round of refactoring into reusable pieces:-- This function is not part of the solution, but it will help you-- understand mapTreeM below.mapTree :: (a -> b) -> Tree a -> Tree bmapTree fn (Tree a subtrees) = let subtrees' = map (mapTree fn) subtrees a' = fn a in Tree a' subtrees'-- Normally you'd write that function like this:mapTree' fn (Tree a subtrees) = Tree (fn a) $ map (mapTree' fn) subtrees-- But I wrote it out the long way to bring out the similarity to the-- following, which extracts the structure of the tagStep definition from-- the first solution above.mapTreeM :: Monad m => (a -> m b) -> Tree a -> m (Tree b)mapTreeM action (Tree a subtrees) = do subtrees' <- mapM (mapTreeM action) subtrees a' <- action a return $ Tree a' subtrees'-- That whole business with getting the state and putting the successor-- in as the replacement can be abstracted out. This action is like a-- post-increment operator.postIncrement :: Enum s => State s spostIncrement = do val <- get put (succ val) return val-- Now tag can be easily written in terms of those.tag init tree = evalState (mapTreeM step tree) init where step a = do tag <- postIncrement return (a, tag)You can make mapTreeM process the local value before the subtrees if you want:mapTreeM action (Tree a subtrees) = do a' <- action a subtrees' <- mapM (mapTreeM action) subtrees return $ Tree a' subtrees'And using Control.Monad you can turn this into a one-liner:mapTreeM action (Tree a subtrees) = -- Apply the Tree constructor to the results of the two actions liftM2 Tree (action a) (mapM (mapTreeM action) subtrees)-- in the children-first order:mapTreeM' action (Tree a subtrees) = liftM2 (flip Tree) (mapM (mapTreeM action) subtrees) (action a) 这篇关于如何在Haskell中装饰一棵树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！ 上岸，阿里云！
