替换n元树中的元素

对于Haskell，我很新，并且在函数式编程时仍然遇到一些问题。随着中说：替换n元树中的元素

我有一个自定义的N叉树数据类型

data Tree = Empty | Leaf String | Node String [Tree]

我试图写一个函数在一棵树上替换元素，即

更换第一个字符串与第二个。每个字符串只有一次发生，所以我可以坚持找到第一个字符串。我已经做了一些努力，但我无法掌握如何在替换元素后重建完整的树。一般来说，我有这个：

ntreeReplace x y (Node z lis) 
    |(x==z) = Just (Node y lis)

这显然只改变了头部node。我写了一个函数，如果元素存在于树中，则返回true，如leaf或node，但超出此范围的进度证明是困难的。

感谢您的帮助！

来源

2009-11-08 blork

我建议你按如下方式为树构造函数。这使得它更通用的，因此更多的功能编程的精神=）数据树一空= |叶a |节点[树一] 获得（...）而你需要做的，基本上是一棵树的地图。 – codebliss 2009-11-08 19:32:13

这很棘手。如果有任何孩子产生匹配，您希望该过程将节点的孩子短路。这是我的解决方案。

import Data.Maybe 

ntreeReplace :: String -> String -> Tree -> Maybe Tree 
ntreeReplace x y (Node z lis) 
    | (x==z) = Just (Node y lis) 
    | otherwise = 
     let (nothings, justs) = span (isNothing . ntreeReplace x y) lis 
     in case justs of 
      [] -> Nothing 
      (t:ts) -> Just (Node z (nothings ++ [fromJust $ ntreeReplace x y t] ++ ts)) 

ntreeReplace x y (Leaf z) 
    | (x==z) = Just (Leaf y) 
    | otherwise = Nothing

nTreeReplace回报Nothing如果有此树（即，我们应该重新使用输入不变）和Just t不匹配，如果进行了替换（即我们应该t更换输入）。我使用span将儿童列表分成Nothing s的前缀和第一个元素匹配的（可能为空）后缀。

该实现的，因为它在一个匹配的孩子叫ntreeReplace两次，可能小的低效率：一次在span谓词，并再次在构建替换节点。

我也推荐一个更高级别的功能replace，它给你一个（可能相同的）Tree，而不是Maybe Tree。

replace :: String -> String -> Tree -> Tree 
replace x y t = 
    case ntreeReplace x y t of 
     Nothing -> t 
     (Just t') -> t'

[编辑]随着@codebliss'建议的线，你可以改变data声明

data Tree a = Empty | Leaf a | Node a [Tree a]

，你就必须改变唯一的其他东西是ntreeReplace和replace签名：

replace :: Eq a => a -> a -> Tree a -> Tree a 
ntreeReplace :: Eq a => a -> a -> Tree a -> Maybe (Tree a)

来源

2009-11-08 18:36:08

非常感谢您的帮助！ – blork 2009-11-08 19:46:06

这里的另一个解决方案，避免了ntreeReplace双号召，在建设了一堆的成本不必要的列表副本。（我不知道哪个更有效。）

我正在使用上面建议的修改后的data定义。

import Data.List 

data Tree a = Empty | Leaf a | Node a [Tree a] 

-- Returns a tree and a boolean flag indicating whether the tree changed 
ntreeReplace :: Eq a => a -> a -> Tree a -> (Bool, Tree a) 

ntreeReplace x y [email protected](Node z ts) 
    | (x==z) = (True, Node y ts) 
    | otherwise = 
     let (changed,ts') = 
       foldl' 
       (\(changed,ts') t -> 
        if changed then (True,t:ts') 
        else 
         let (changed,t') = ntreeReplace x y t 
         in (changed,t':ts')) 
       (False,[]) 
       ts 
     in 
      if changed then (True, Node z $ reverse ts') 
      else (False,t) 

ntreeReplace x y [email protected](Leaf z) 
    | (x==z) = (True, Leaf y) 
    | otherwise = (False,t)

来源

2009-11-09 23:31:47

替换n元树中的元素

回答

相关问题