5

给出了两种数据类型 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

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

4

3 回答 3

5

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

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'. 鉴于我们看到 a Leaf，我们不需要对值执行任何操作，我们只需返回我们的叶子结果l：

fold_plant' Leaf = l

如果我们找到(Blossom c)带有c颜色的 a，我们必须执行从 ac :: Color到x带有b部件的映射以获得新值：

fold_plant' (Blossom c) = b c

最后，如果我们有 a Stalk，我们将不得不执行递归：我们首先调用fold_plant'左茎，然后调用 the并使用两个结果fold_plant'构造 an ：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)
于 2017-07-04T22:32:00.167 回答
3

fold 是一个函数，它在结构中获取一段数据，并将其折叠为另一段数据。通常我们这样做是为了将集合“减少”为单个值。这就是为什么如果您查看其他语言，如 Lisp、Smalltalk、Ruby、JavaScript 等，您会发现这个操作称为reduce，它是 Haskell 中折叠的可怜表亲。

我说这是可怜的表弟，因为你对列表的直觉是正确的，但是在 Haskell 中我们更加抽象和通用，所以我们的折叠函数可以在任何类型的结构上工作，我们已经告诉 Haskell 折叠意味着什么。

因此，我们可以谈论“使用加法和折叠将数字列表转换为和值”，或者我们可以谈论“使用函数获取名称的家谱并将其折叠为列表”，等等等等。任何时候我们有这种将某物的结构更改为单个值，或者可能是不同的结构化值集的想法，这就是折叠。

在 Haskell 中表示这一点的“规范”方式是，foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b但它更容易，就像您认为在开始时使用“列表a”作为Foldable f => t a类型一样，因为它更容易理解。所以我们有一个专门的类型foldr :: (a -> b -> b) -> b -> [a] -> b。但是a和是什么b？这三个论点是(a -> b -> b)什么，有什么作用？

让我们将它专门Int用于两者的值a：b哇foldr :: (Int -> Int -> Int) -> Int -> [Int] -> Int……这使它……很有趣，不是吗？所以foldr需要两个整数的函数，比如(+)函数，它需要一个Int值（这是它将用作目标结果的初始值，以及一个Int值列表......然后它将产生一个Int从那......也就是说，它采用该Int -> Int -> Int函数并将其应用于单个Int和第一个[Int]，然后将该函数应用于该结果和下一个值，[Int]依此类推，直到没有更多[Int]剩余。 ..然后这就是它返回的内容。

它实际上是在数据结构上折叠函数。

对于列表来说，这一切都很好，它是一条直线，但你拥有的是一棵树，而不是列表。那么它是如何在那里工作的呢？好吧，让我们看看我们如何专门foldr从列表中生成一对最高和最低的数字Int？foldr :: (Int -> (Int, Int) -> (Int, Int)) -> (Int, Int) -> [Int] -> (Int, Int). 因此，我们采用一个带有一个Int和一对的函数，并将初始对放入其中，以及Int我们的第一个对[Int]。这将返回一个新的对，然后我们对下一个执行相同的过程[Int]，然后我们继续该过程，直到最后剩下的就是一对。

foldToMinMax = foldr (\newNum (minnum,maxnum) -> (min minnum newNum, max maxnum newNum)) (maxBound :: Int, minBound :: Int)

所以现在事情变得更清楚了。

不过，你的这棵花树呢？好吧，您需要为自己编写一个折叠函数，该函数将采用两个值，其中一个与初始值和结果值相同，另一个是您的树的类型，并构建一个值结果类型的。如果我要使用伪代码以更具描述性的方式编写类型，我可能会编写如下内容：foldr :: (contentOfCollectionType -> resultType -> resultType) -> resultType -> (collectionWrapper contentOfCollectionType) -> resultType

但是你不必foldr在这里使用，事实上你不能使用它，除非你做一些花哨的类型类实例化的东西。您完全可以使用普通递归编写自己的折叠函数。这就是他们所追求的。

如果你想学习递归和折叠之类的，而且你还不了解这些东西，我推荐我帮助编写的书。http://happylearnhaskelltutorial.com它更详细地解释了它，并提供了许多清晰的示例。如果您了解基础知识，应该很快就可以快速了解您想了解递归和折叠的点......但是如果您不了解，那么了解基础知识，因为您需要在了解其他内容之前了解它们。

我应该提到你的特定折叠也有一个转换功能。它是将 a 转换为 的Color东西x。您被赋予作为折叠函数使用的函数“将 x 压在一起”（即采用两个x值并产生另一个x值，与我们上面的示例非常相似(+)）。它只能在树上工作，因为我们也给它这个函数来把 aColor变成 a x，这有效地从树中取出有意义的数据并将其放入折叠函数可以使用的形式。

这里有一个非常漂亮的模式。

祝你好运！

于 2017-07-05T11:38:13.533 回答
1

折叠是递归问题解决的本质：

    data Plant =                        data Result r =    
         Leaf                                RLeaf 
       | Blossom Color                     | RBlossom Color
       | Stalk Plant Plant                 | RStalk r r
            -- recursive data           -- non-recursive data: `r`, not `Result r`!

递归问题求解是以一种简单的方式组合递归处理原始结构的组成部分的结果：

    -- single-step reduction semantics:
    -- reduction_step :: ..... -> Result r -> r
    reduction_step :: (r -> r -> r) -> (Color -> r) -> r -> Result r -> r
    reduction_step s b l  RLeaf       = l
    reduction_step s b l (RBlosom c)  = b c
    reduction_step s b l (RStalk x y) = s x y

但是要达到这一点，我们需要递归到与整个结构具有相同性质的原始结构的组成部分，因此fold_plant我们寻求创建的过程可以应用于它们，就好像已经编写好了（递归！ ):

    recurse_into :: (r -> r -> r) -> (Color -> r) -> r -> Plant -> Result r
    recurse_into s b l Leaf          = RLeaf
    recurse_into s b l (Blossom c)   = RBlossom c
    recurse_into s b l (Stalk lt rt) = RStalk (fold_plant s b l lt) (fold_plant s b l rt)

所以，最后，我们的折叠只是两者的组合，

    fold_plant :: (r -> r -> r) -> (Color -> r) -> r -> Plant -> r
    fold_plant s b l plant = reduction_step s b l          --          Result r -> r
                               (recurse_into s b l plant)  -- Plant -> Result r

一定要遵循这些类型，并说服自己一切都应该结合在一起。

当然可以避免临时数据定义和折叠函数定义，但这是要遵循的一般过程。

（参见递归方案）。

于 2017-07-05T13:21:35.007 回答