替換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元樹中的元素

回答

相關問題