3

My Tree definition is as follows:

data Tree a = Leaf a | Node (Tree a) (Tree a) deriving (Show)

I want to write a filter function that picks only every 3rd element of an array (1st, 4th, 7th, ...). As an example, suppose my tree is as follows:

Node 
    (Node 
        (Node 
            (Leaf 'a') 
            (Leaf 'b')) 
        (Leaf 'c'))
    (Node 
        (Node 
            (Leaf 'd') 
            (Leaf 'e')) 
        (Leaf 'f'))

Then the filter function should result in a new tree as:

Node (Leaf 'a') (Leaf 'd')
4

1 回答 1

4

这是给你的游戏计划。

  1. 编写一个函数，将函数应用于树的每个元素。 

    mapTree :: (a -> b) -> Tree a -> Tree b

    （奖励：创建Tree一个Functor实例，并使用fmap代替mapTree）

  2. 编写一个函数，按照从左到右出现的顺序标记树的元素。

    labelTree :: Tree a -> Tree (Integer, a)

    （提示：您将需要一个辅助函数，它接受一个“当前标签”并返回带标签的树以及一个新标签；即:: Integer -> Tree a -> (Tree (Integer, a), Integer)。这个函数的分支情况如下：

    aux n (Branch l r) = 
    let (l', n')  = aux n l
        (r', n'') = aux n' r in
    (Branch l' r', n'')

    仔细阅读这段代码，然后看看能不能拿出Leaf案例）

    State（奖励：使用monad来做）

  3. 编写一个函数，删除树中不满足条件的元素。

    filterTree :: (a -> Bool) -> Tree a -> Maybe (Tree a)

    请注意，我们返回 aMaybe (Tree a)而不仅仅是 a Tree a- 这是因为如果没有元素匹配条件，我们需要返回一些东西，并且您的Tree类型不允许空树。碰巧返回 aMaybe (Tree a)也使得这个函数很容易递归地编写。

  4. 结合这些函数来获得你正在寻找的函数——只过滤掉标签可以被 3 整除的元素。

以这种方式分解它的好处是，除了解决您的特定问题之外，您还为自己编写了许多通常有用的工具来处理您的Tree类型。映射和过滤器是实现数据结构时出现的非常常见的功能。

高级：State monad Bonus 实现是另一种称为“遍历”的常见函数类型的labelTree特定情况 ：

traverse :: (Applicative f) => (a -> f b) -> Tree a -> f (Tree b)

这就像一张地图，但也结合了每个元素上可能发生的“效果”。如果你能实现它，然后用它来写，超级双加奖金labelTree。

于 2013-06-12T05:10:02.183 回答