在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”。

我已经看到了一些树的示例，它们在同一个数据部分中，并且构造函数相似。

在Python世界中，我只需遍历列表，匹配所需内容并替换值即可。

在Haskell中，我猜我需要能够复制我的树，但是如何处理嵌入在构造函数和不同数据类型中的列表呢？

- Chris

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" []]。

希望这可以帮助你！

- Martijn

---

谢谢。这就是我要找的。 要使其工作，我必须导入Data.Generics。 - Chris

太棒了。很高兴这里有人知道如何让SYB工作。+1 - Norman Ramsey

Answer 2

我不知道你问题的一般答案。这种数据类型相当假造，我可能会选择实现一个折叠而不是过滤器。不过，下面是一些可以更新所有四个位置的字符串的过滤函数。我已经将代码通过编译器，所以它已经进行了类型检查，但我还没有运行它。

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)

- Norman Ramsey

---

有趣。这个例子是人为制造的，因为我正在使用Parsec创建一个语言的抽象树。所以你会得到表达式中的表达式和各种其他奇怪的扭曲。所以你的意思是说，为我想要操作的每个对象创建一个SFilter。我唯一看到的问题是实际的树非常大，有许多类型。这是一个非常好的例子，我认为我可以解决它。 - Chris

@Chris：如果你的树类型互相递归，由于静态类型系统，每个类型都需要一个函数处理，没有其他解决方法。我曾使用类型类来处理这种复杂性，或者如果你勇气十足，可以尝试 "Scrap Your Boilerplate" 或 Ralf Hinze's 的"Generic Programming for the Masses" 或 "Generics Now"。 - Norman Ramsey

是的，看起来你要找的关键词是“泛型编程”。 - Wei Hu

我已经通过编译器运行了代码，所以它可以进行类型检查，但我还没有运行它。哎呀，你怎么能错过一个完美的引用 Knuth 的机会呢？鉴于 Curry-Howard 对应原理，这几乎是 "Beware of bugs in the above code; I have only proved it correct, not tried it." 的意思。 - C. A. McCann

Answer 3

您希望遍历整个数据结构并在其中更改一些项目。通常可以通过将数据结构作为参数传递给函数并返回新的、更改过的结构版本来完成此操作。

对于每种输入情况，该函数定义了应返回的新值的样式。

修改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。在命令式语言中，您通常会使用五个for循环来代替五个map调用。

也许您可以简化数据结构以减少此“开销”。当然，这取决于您的实际用例，但例如，您可能不需要Data2情况： DataA2 "abc"和DataA3 "abc" []之间有区别吗？

- sth

---

我所举的例子实际上只是来自解析语言的抽象树的一小部分。因此，我可能可以简化它，但不能简化到比您看到的要简单得多的程度。这是一个不错的方法，我需要修改它，以便我可以将其用于许多不同的过滤器。基本上，我正在尝试使用几个过滤器来修改这个解析后的语言，以便可以将其漂亮地打印出来，以供另一种语言使用。 - Chris

Answer 4

您可能想要查看multirec库，以处理相互递归的数据类型。我并没有使用过它，但从您描述的情况来看，它似乎正是针对您正在处理的问题。它使用了像其他答案中建议的通用编程技术，但可能可以为您节省实现所有功能所需的时间。

- C. A. McCann