Обход и фильтрация дерева в haskell

Question

Я довольно новичок в Haskell (все еще работаю над полным пониманием монад). У меня проблема, когда у меня есть древовидная структура

type Tree = [DataA]

data DataA =  DataA1 [DataB] 
            | DataA2 String 
            | DataA3 String [DataA]
               deriving Show

data DataB =  DataB1 [DataA] 
            | DataB2 String 
            | DataB3 String [DataB]
               deriving Show

То, что я хотел бы сделать, - это пройти через это и сгенерировать новое дерево с фильтром. Например, я могу захотеть изменить все DataB2 в дереве на «foo».

Я видел примеры дерева, когда они находятся в одном и том же разделе данных, и конструкторы похожи.

В мире питонов я просто просматривал список, сопоставлялся с тем, что мне было нужно, и заменял значение.

В Хаскеле я предполагаю, что мне нужно иметь возможность копировать мое дерево, но как вы справляетесь со списками, похороненными в конструкторах и разных типах данных?

Answer 1

Для этого вы можете использовать общее программирование.

Одна такая универсальная библиотека программирования называется Scrap Your Boilerplate. В самом верху вашего модуля включите Scrap Your Boilerplate, написав:

{-# LANGUAGE DeriveDataTypeable #-}

Модуль импорта Data.Generics. Затем, кроме Show, также получите Typeable и Data экземпляров для ваших типов данных.

Теперь вы можете написать запрошенную функцию следующим образом:

toFoo :: Data a => a -> a
toFoo = everywhere (mkT step)
  where
    step (DataA2 _)  = DataA2 "foo"
    step x           = x

Это все, что вам нужно сделать, чтобы сделать эту работу. Например, когда вы звоните toFoo [DataA1 [], DataA2 "hi", DataA3 "yo" []], ответ будет [DataA1 [],DataA2 "foo",DataA3 "yo" []].

Надеюсь, это поможет!

Answer 2

Вы хотите просмотреть всю структуру данных и изменить некоторые элементы здесь и там. Обычно это делается функцией, которая принимает структуру данных в качестве параметра и возвращает новую, измененную версию структуры.

Для каждого случая ввода эта функция определяет, как должно возвращаться новое значение похож.

Основная функция, которая изменяет Tree (это просто список DataA значений) вероятно, следует просто вернуть новый список измененных значений. Если мы отложим эти модификация значений для функции modifyA, основная модификация функция выглядит так:

-- # function to change a |Tree|
mutate :: Tree -> Tree
mutate as = map mutateA as
     -- # (The |map| function applies the |mutateA| function to every
     -- #  element of |as|, creating a list of all the return values)

Теперь необходимо определить функцию mutateA, чтобы изменить все возможные значения DataA, и лучше всего это сопровождается функцией mutateB, которая обрабатывает значения DataB.

Эти функции смотрят на различные возможные случаи значений и возвращают соответствующие новые значения:

-- # function to change |DataA| items
mutateA :: DataA -> DataA
     -- # A |DataA1| is a |DataA1| with modified values
mutateA (DataA1 bs)   = DataA1 (map mutateB bs)
     -- # A |DataA3| is a |DataA3| with modified values
mutateA (DataA3 s as) = DataA3 s (map mutateA as)
     -- # In the remaining case(s) the value stays the same
mutateA d             = d

-- # function to change |DataB| items
mutateB :: DataB -> DataB
mutateB (DataB1 as) = DataB1 (map mutateA as)
mutateB (DataB3 s bs) = DataB3 s (map mutateB bs)
     -- # Here comes a real change
mutateB (DataB2 _)  = DataB2 "foo"

Таким образом, для каждого элемента в дереве вычисляется новый элемент, где все DataB2 значения в любом месте дерева заменяются на «foo».

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

Возможно, вы могли бы упростить структуру данных, чтобы уменьшить эти «накладные расходы». это конечно, зависит от вашего фактического варианта использования, но, может быть, например, вам не нужно случаи Data2: Есть ли разница между DataA2 "abc" и DataA3 "abc" []?

Answer 3

Я не знаю общего ответа на ваш вопрос. Тип данных довольно надуманный, и я, вероятно, предпочел бы реализовать сгиб, а не фильтр. Здесь, однако, есть некоторые функции фильтра, которые могут обновлять строки во всех четырех позициях. Я поместил код через компилятор, поэтому он проверяет тип, но я не запускал его.

type SFilter = String -> String

-- to filter a tree, say how A2, A3, B2, and B3 should be changed

type Filter tree = SFilter -> SFilter -> SFilter -> SFilter -> (tree -> tree)

afilter :: Filter DataA
bfilter :: Filter DataB
tfilter :: Filter Tree

tfilter a2 a3 b2 b3 = map (afilter a2 a3 b2 b3)
afilter a2 a3 b2 b3 = fil
  where fil (DataA1 bs)   = DataA1 $ map (bfilter a2 a3 b2 b3) bs
        fil (DataA2 s)    = DataA2 (a2 s)
        fil (DataA3 s as) = DataA3 (a3 s) (map fil as)

bfilter a2 a3 b2 b3 = fil
  where fil (DataB1 as)   = DataB1 $ map (afilter a2 a3 b2 b3) as
        fil (DataB2 s)    = DataB2 (b2 s)
        fil (DataB3 s bs) = DataB3 (b3 s) (map fil bs)

Answer 4

Возможно, вы захотите взглянуть на библиотеку multirec для работы со взаимно рекурсивными типами данных. Я не использовал его, но из того, что вы описали, звучит так, будто он нацелен именно на проблему, с которой вы работаете. Он использует общее программирование, как предлагали другие ответы, но может сэкономить вам время на самостоятельную реализацию.