9

我对 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 中，我猜我需要能够复制我的树，但是你如何处理隐藏在构造函数和不同数据类型中的列表？

4

4 回答 4

11

您可以为此使用通用编程。

一个这样的通用编程库称为 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" []]。

希望这可以帮助！

于 2010-02-26T10:55:39.040 回答
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)
于 2010-02-26T00:41:12.077 回答
2

您想遍历整个数据结构并在这里和那里更改一些项目。这通常由一个函数完成，该函数将数据结构作为参数并返回结构的新更改版本。

对于每种输入情况，此函数都定义了返回的新值的外观。

Tree修改 a （这只是一个值列表）的基本函数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" []

于 2010-02-26T00:54:58.630 回答
0

您可能想查看用于处理相互递归数据类型的multirec库。我没有使用过它，但从您所描述的情况来看，它听起来像是针对您正在处理的那种问题。它像这里的其他答案所建议的那样使用通用编程，但可能会节省您自己实现所有内容的时间。

于 2010-02-26T15:03:04.167 回答