haskell - 我将如何实现这个折叠功能？

Question

给出了两种数据类型颜色和植物。

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 Stalk Blossom Leaf是植物的身份。

现在我知道在 Haskell 中你可以创建这样的函数:

fold_plant :: (x -> x -> x) -> (Color -> x) -> x -> Plant -> x
fold_plant = do something

但从这里开始，我不知道折叠功能如何对植物起作用。

Answer 1

如果我们看一下函数签名:

fold_plant :: (x -> x -> x) -> (Color -> x) -> x -> Plant -> x
--            \_____ _____/    \____ _____/    |      |      |
--                  v               v          v      v      v
--                stalk           blossom     leaf  tree  output

我们看到有 stalk部分以及 blossom部分和一个 leaf部分。我们将命名 stalk功能 s和 blossom功能 b这里和 leaf零件l .为了简化(和优化)函数，我们将这三个参数解包，然后调用一个递归方法:

fold_plant s b l = fold_plant'
    where fold_plant' = ...

现在的问题当然是如何处理 fold_plant' .鉴于我们看到一个 Leaf ，我们不需要对值执行任何操作，我们只需返回我们的叶子结果 l :

fold_plant' Leaf = l

如果我们找到 (Blossom c)与 c一种颜色，我们必须从 c :: Color 执行映射到 x与 b获取新值的部分:

fold_plant' (Blossom c) = b c

最后，万一我们有 Stalk我们将不得不执行递归:我们首先调用 fold_plant'在左边的茎上，然后我们调用 fold_plant'并构造一个 s有两个结果:

fold_plant' (Stalk lef rig) = s (fold_plant' lef) (fold_plant' rig)

所以我们可以把它放在下面的函数中:

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' rig)