编写一个计算玫瑰树中元素数量的函数

Question

编写一个计算玫瑰树中元素数量的函数。

我试过计算一​​棵玫瑰树中元素的数量。

data RoseTree a = RoseNode a [RoseTree a]
    deriving Show
things :: RoseTree String
things = 
    RoseNode "thing" [
        RoseNode "animal" [
            RoseNode "cat" [], RoseNode "dog" []
        ],

        RoseNode "metal" [
            RoseNode "alloy" [
                RoseNode "steel" [], RoseNode "bronze" []
            ],
            RoseNode "element" [
                RoseNode "gold" [], RoseNode "tin" [], RoseNode "iron" []
            ]
        ],

        RoseNode "fruit" [
            RoseNode "apple" [
                RoseNode "Granny Smith" [], RoseNode "Pink Lady" []
            ],
            RoseNode "banana" [],
            RoseNode "orange" []
        ],

        RoseNode "astronomical object" [
            RoseNode "Planet" [
                RoseNode "Earth" [], RoseNode "Mars" []
            ],
            RoseNode "Star" [
                RoseNode "The Sun" [], RoseNode "Sirius" []
            ],
            RoseNode "Galaxy" [
                RoseNode "Milky Way" []
            ]
        ]
    ] 

它应该是27，但是它返回4。

编辑：这是我的尝试：

roseSize x = case x of
    RoseNode a [] -> 0
    RoseNode a (x:xs) -> 1 + roseSize (RoseNode a xs)

Answer 1

它应该是27，但是它返回4。

roseSize x = case x of
  RoseNode a [] -> 0
  RoseNode a (x:xs) -> 1 + roseSize (RoseNode a xs)

因此，您无需递归计算子树。试一试（固定为：基本情况为1）

roseSize (RoseNode _ []) = 1
roseSize (RoseNode a (t:ts)) = roseSize t + roseSize (RoseNode a ts)

缺少的部分是roseSize t。

否则，您将只对树的第一层进行递归调用。

如果您手动评估功能，这很明显，

roseSize things
  ~> roseSize (RoseNode "thing" [ animals, metals, fruits, astronomical_objects ]
  ~> 1 + roseSize (RoseNode "thing" [ metals, fruits, astronomical_objects ])
  ~> 1 + 1 + roseSize (RoseNode "thing" [ fruits, astronomical_objects ])
  ~> 1 + 1 + 1 + roseSize (RoseNode "thing" [ astronomical_objects ])
  ~> 1 + 1 + 1 + 1 + roseSize (RoseNode "thing" [])
  ~> 1 + 1 + 1 + 1 + 0

而roseSize t在功能体内，评估变为

roseSize things
  ~> roseSize (RoseNode "thing" [ animals, metals, fruits, astronomical_objects ]
  ~> roseSize animals
      + roseSize (RoseNode "thing" [ metals, fruits, astronomical_objects ])
  ~> roseSize (RoseNode "animal" [ cat, dog ])
      + roseSize (RoseNode "thing" [ metals, fruits, astronomical_objects ])
  ~> roseSize cat
      + roseSize (RoseNode "animal" [ dog ])
      + roseSize (RoseNode "thing" [ metals, fruits, astronomical_objects ])
  ~> 1 -- given the base case of 1 instead of 0
      + roseSize (RoseNode "animal" [ dog ])
      + roseSize (RoseNode "thing" [ metals, fruits, astronomical_objects ])
  ~> ...

作为练习，使此函数显式递归是可以的。

但是您可能要考虑使用更通用的方法，或者使用像PF这样的高阶函数。卡斯特罗（Castro）做到了，或者像这样Data.Tree的现有数据结构containers：

import qualified Data.Tree as T
import           Data.Tree (Tree(..))

things :: Tree String
things = Node "thing" [ animals, metals, fruits, astronomical_objects ]
  where
    animals = Node "animal" (map pure [ "cat", "dog" ])
    metals = Node "metal" [ alloys, elements ]
    alloys = Node "alloy" (map pure [ "steel", "bronze" ])
    elements = Node "element" (map pure [ "gold", "tin", "iron" ])
    fruits = ...
    astronomical_objects = ...

由于a Data.Tree是Foldable，因此可以length在其上使用。

因此，没有必要定义自定义roseSize函数。

此时，您正在计算树中的节点，而不是树的叶子，叶子是实际对象，而不是它们所属的类别。因此，您可能实际上对计数叶子感兴趣。

您可以通过创建一个查找叶子的函数来做到这一点：

leaves :: Tree a -> [a]
leaves (Node x []) = ... -- x is a leaf
leaves (Node _x ts) = ... -- _x isn't a leaf

使用此模板，您不能轻松地使用显式递归，即在on上进行匹配Node x (t:ts)并leaves在on上调用ts，因为非叶子案例最终以基本案例结束，使得用尽的类别显示为叶子。但是你可以使用高阶函数抽象出递归，例如concat，map或concatMap的Prelude。

使用库玫瑰树还具有其他优点，例如，一堆其他类型类实例（Applicative使您pure "foo"可以构造单例树/叶子）和漂亮的打印功能：

> putStrLn $ T.drawTree things
thing
|
+- animal
|  |
|  +- cat
|  |
|  `- dog
|
`- metal
   |
   +- alloy
   |  |
   |  +- steel
   |  |
   |  `- bronze
   |
   ...