如何在Haskell中装饰一棵树 [英] How to decorate a Tree in Haskell

问题描述

我想用一个不同的值来标记树的每个元素（例如，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'< -  action 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 constructor    
data 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 b
mapTree 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 s
postIncrement = 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中装饰一棵树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！