Замена элемента в n-арном дереве

Я довольно новичок в Haskell, и у меня все еще есть некоторые проблемы с функциональным программированием. При этом сказал:

У меня есть собственный тип данных n-арного дерева

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

Я пытаюсь написать функцию для замены элемента в дереве, т.е.

replaceInTree :: String -> String -> Tree -> Maybe Tree

Замена первой строки на вторую. Каждая строка встречается только один раз, поэтому я могу придерживаться первого найденного. Я приложил несколько усилий, но не могу понять, как восстановить полное дерево после замены элемента. Тривиально, у меня есть это:

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

который, очевидно, меняет только голову node. Я написал функцию, которая возвращает true, если элемент присутствует в дереве, как leaf или node, но продвижение дальше этого оказалось затруднительным.

Спасибо за любую помощь!


tree haskell
person blork    schedule 08.11.2009    source источник
comment
Я бы рекомендовал вам сделать конструктор для дерева следующим образом. Это делает его более общим и, следовательно, более соответствующим духу функционального программирования =) Дерево данных a = Empty | Лист а | Узел a [Tree a] производный (...) И что вам нужно сделать, так это карту для дерева.   -  person codebliss    schedule 08.11.2009

Ответы (2)


arrow_upward
2
arrow_downward

Это сложно. Вы хотите, чтобы процесс замыкался на дочерних элементах узла, если какой-либо дочерний элемент производит совпадение. Вот мое решение.

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 для разделите список дочерних элементов на префикс Nothings и (возможно, пустой) суффикс, где первый элемент имеет совпадение.

Эта реализация имеет возможную небольшую неэффективность, поскольку она дважды вызывает 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'

[EDIT] В соответствии с предложением @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)
person Chris Conway    schedule 08.11.2009

arrow_upward
0
arrow_downward

Вот еще одно решение, позволяющее избежать двойного вызова 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 t@(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 t@(Leaf z)
    | (x==z) = (True, Leaf y)
    | otherwise = (False,t)
person Chris Conway    schedule 09.11.2009