如何用这个折叠功能计算植物的叶子数量？

Question

Color 和 Plant 是数据类型，定义如下：

data Color = Red | Pink | White | Blue | Purple | Green | Yellow
   deriving (Show, Eq)

data Plant=
      Leaf
   |  Blossom Color
   |  Stalk Plant Plant
   deriving (Show, Eq)

折叠函数是这样的：

fold_plant :: (x -> x -> x) -> (Color -> x) -> x -> Plant -> x
fold_plant s b l = fold_plant'
    where fold_plant' Leaf = l
          fold_plant' (Blossom c) = b c
          fold_plant' (Stalk lef rig) = s (fold_plant' lef) (fold_plant' right)

现在我应该实现一个函数 amount，它使用 fold 函数，将 Plant 作为参数，returns 植物中的叶子数量。我认为我现在面临的主要问题是我应该使用的折叠功能不像通常的折叠功能那样工作。我的意思是像 foldr 和 foldl，因为它们有 3 个参数：一个函数、一个初始值和一个列表。但是在我的函数 fold_plant 中只有 none 个。

这是我考虑使用的，但我认为我没有正确理解所有内容。

amount :: Plant-> Integer
amount input = length . filter (Leaf ==) fold_plant Stalk Blossom Leaf input

Answer 1

不，这个想法通常是使用fold_plant作为计算树叶数量的方法。你可以这样做：

amount :: Num n => Plant -> n
amount = fold_plant (+) (const 0) 1

所以这意味着：

对于每一个Stalk x y，我们折叠它并且return两个children的叶子数的总和;
对于每个 Blossom x，我们 return 0（因为我们在颜色 x 上调用 const 0，并且 const 0 [=每个输入 45=]s 0）；和
对于每个 Leaf，我们 return 一个 1。

因此，由于每个叶子都映射到 1，每个 Blossom 映射到 0，并且 Stalk 作为加法 (+) 运算符，我们获取叶子总数。

Answer 2

另一个答案直接跳到解决方案，然后捍卫该解决方案是正确的。在这个答案中，我想转向另一个方向：描述一种您可以自己发明解决方案的方法。

我假设您自己首先可以 编写此函数而无需 折叠，仅使用基本的模式匹配和递归。以下是您可能想到的（可能是模数命名）：

amount Leaf = 1
amount (Blossom c) = 0
amount (Stalk lef rig) = amount lef + amount rig

现在与这个折叠的简化定义（不使用 where-block 辅助函数）进行比较：

fold_plant s b l Leaf = l
fold_plant s b l (Blossom c) = b c
fold_plant s b l (Stalk lef rig) = s (fold_plant s b l lef) (fold_plant s b l rig)

天哪，这两个定义看起来很相似！让我们假设 amount = fold_plant s b l 对于 s、b 和 l 的某些选择。查看前两个等式：

amount           Leaf = 1
fold_plant s b l Leaf = l

所以我们应该选择l = 1。对于后两个方程：

amount           (Blossom c) = 0
fold_plant s b l (Blossom c) = b c

所以我们应该选择b c = 0。最后两个等式：

amount           (Stalk lef rig) = amount lef + amount rig
fold_plant s b l (Stalk lef rig) = s (fold_plant s b l lef) (fold_plant s b l rig)

嗯，回想一下我们的假设是amount = fold_plant s b l，所以

s (fold_plant s b l lef) (fold_plant s b l rig) = s (amount lef) (amount rig)

两个等式现在是：

amount           (Stalk lef rig) = amount lef + amount rig
fold_plant s b l (Stalk lef rig) = s (amount lef) (amount rig)

所以我们应该选择s x y = x + y。一下子写下这些方程式，我们得出了答案：

amount = fold_plant s b l where
    l = 1
    b c = 0
    s x y = x + y

如何用这个折叠功能计算植物的叶子数量？

How to count the number of leaves of a plant with this fold function?

tree

haskell

fold