haskell 遍历一棵玫瑰树，直到满足某些条件，然后修改树

plupiseo 于 2023-02-04 发布在其他

关注(0)|答案(1)|浏览(127)

我在Haskell中有两棵玫瑰树，分别有 m 和 n 个节点，我想用第二棵树的 jth 个节点替换第一棵树的 ith 个节点。
例如：
树1：

R                                                           
  _________|____________                 
  |        |           |
  A        B           C
 / \      / \         / \
D   E    F   G       H   I

树2：

r
  _____|____
  |         |       
  P         Q       
 / \      / | \      
S   T    U  V  W

则用树2节点4（Q）替换树1节点7（C）的结果树应该是（假设索引是预先排序的并且从0开始）

R                                                           
  _________|____________                 
  |        |           |
  A        B           Q
 / \      / \        / | \
D   E    F   G      U  V  W

我试过使用zippers，但我的问题是我无法解决如何将zippers的焦点放在 ith 元素上，
例如，如何实现以下类型的函数：
someFunc :: Tree a -> Int -> Zipper a
其取得树的根并遍历它（以某种顺序）以返回集中于第i个预排序节点和上下文的zipper。
从树库中我可以使用flatten将一棵树扁平化为一个预先排序的值列表，我可以稍微改变一下，给予我一个树列表。

flattenToTreeList :: Tree a -> [Tree a]
flattenToTreeList t = squish t []
  where squish (Node x ts) xs = Node x ts : foldr squish xs ts

如果我可以用拉链来做这个，那么这个列表的第i个元素会满足我，但是我迷失了，现在在绕圈子。

haskell

来源：https://stackoverflow.com/questions/75302885/traverse-a-rose-tree-until-some-condition-is-met-then-modify-tree

1条答案

按热度按时间

fhg3lkii1#

嗯，我的评论有点错误。我有点误读了需求，但是在某种程度上实际上减少了一些依赖性。

-- lens
import Control.Lens ((^?), contexts, cosmos, elementOf, ix)

-- containers
import Data.Tree (Tree(..))

-- adjunctions
import Control.Comonad.Representable.Store (peeks)

tree1 :: Tree Char
tree1 = Node 'R' [ Node 'A' [Node 'D' [], Node 'E' []]
                 , Node 'B' [Node 'F' [], Node 'G' []]
                 , Node 'C' [Node 'H' [], Node 'I' []]
                 ]

tree2 :: Tree Char
tree2 = Node 'R' [ Node 'P' [Node 'S' [], Node 'T' []]
                 , Node 'Q' [Node 'U' [], Node 'V' [], Node 'W' []]
                 ]

-- Replace subtree i in t1 with subtree j in t2
-- returns Nothing if either index doesn't exist
replace :: Int -> Tree a -> Int -> Tree a -> Maybe (Tree a)
replace i t1 j t2 = update =<< replacement
  where
    update u = peeks (const u) <$> contexts t1 ^? ix i
    replacement = t2 ^? elementOf cosmos j

main :: IO ()
main = print $ replace 7 tree1 4 tree2

这增加了对adjunctions包的依赖，但它是对透镜的依赖，所以这是一个额外的导入，但不需要额外的包，作为交换，它根本不需要使用树遍历。
这与通常的lens代码有点不同，因为cosmos和contexts都不是特别常见，但它们是处理自相似数据类型的子结构的好工具，这是替换子树的完美描述。
这使用了概念上相当沉重的工具，但我认为意义很好地表达了出来。

赞(0）回复(0）举报 2023-02-04

我来回答

haskell 遍历一棵玫瑰树，直到满足某些条件，然后修改树

1条答案

相关问题

热门标签

最新问答