我该如何实现这种折叠功能？

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 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功能.为了简化(和优化)函数,我们将解包这三个参数,然后调用递归方法:bleafl

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

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

fold_plant' Leaf = l

如果我们找到一个(Blossom c)有c颜色,我们必须执行从一个映射c :: Color到x与b部分来获得新的价值:

fold_plant' (Blossom c) = b c

最后,如果我们有一个,Stalk我们将不得不执行递归:我们首先调用fold_plant'左边的stalk,然后我们调用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)