4

试图理解 Monad 和 Foldable 之间的关系。我知道 Monad、Applicative 和 Functor 类型类的部分价值在于它们能够将函数提升到结构之上，但是如果我想为 Monad 中包含的值生成一个汇总值（例如最小值或最大值）怎么办？

如果没有累加器权利（如可折叠），这将是不可能的吗？为了拥有一个蓄能器，你必须注入或破坏结构？

min :: Ord a => a -> a -> a

foldMin :: (Foldable t, Ord a) => t a -> Maybe a
foldMin t = foldr go Nothing t
  where
    go x Nothing = Just x
    go x (Just y) = Just (min x y)

这里，Nothing 值是累加器。所以不可能在do块的范围内执行产生这样的汇总值的操作吗？

4

3 回答 3

3

我不完全确定我理解这个问题，所以如果这不是一个有用的答案，请原谅我，但据我所知，问题的核心是：

所以不可能在do块的范围内执行产生这样的汇总值的操作吗？

没错，那是不可能的。Haskell 的do符号是语法糖 over Monad，所以基本上是语法糖 over >>=and return。

return，如您所知，不允许您“访问” 的内容Monad，因此对您拥有的内容的唯一访问是 via >>=，例如，在 list monad 的情况下，它只会给您一个值 a时间。

请注意，Foldable它甚至不需要数据容器是 a Functor（更不用说 a 了Monad）。众所周知，Set不是一个Functor实例，但它是一个Foldable实例。

例如，您可以找到一组中的最小值：

Prelude Data.Foldable Set> foldr (\x -> Just . maybe x (min x)) Nothing $ Set.fromList [42, 1337, 90125, 2112]
Just 42
于 2018-11-10T08:14:13.917 回答
3

下面的人为且效率低下的代码是我能得到的最接近“仅使用列表单子”的代码。这可能不是 OP 正在寻找的，但它就在这里。

我还利用head（如果我们想要整体，你可以用 替换它listToMaybe）和null. 我也使用empty（您可以用 替换[]）。

该代码通过非确定性地选择一个元素m然后检查是否不存在更大的元素来工作。这具有二次复杂度。

import Control.Applicative

maximum :: Ord a => [a] -> a
maximum xs = head maxima
   where
   isMax m = null $ do
      x <- xs
      if x > m
         then return x
         else empty
   maxima = do
      m <- xs   -- non deterministically pick a maximum
      if isMax m
         then return m
         else empty
于 2018-11-10T10:58:14.723 回答
0

我也不确定实际的问题是什么，但是可以通过Monoid实例隐藏对累加器的需求。然后 - 对于您的最小示例 - 您可以使用 use foldMapfromData.Foldable来映射和合并Foldable. 例如：

data Min a = Min { getMin :: Maybe a } deriving Show

instance Ord a => Monoid (Min a) where
  mempty                                = Min Nothing
  mappend a (Min Nothing)               = a
  mappend (Min Nothing) b               = b
  mappend (Min (Just a)) (Min (Just b)) = Min (Just (min a b))

foldMin :: (Foldable t, Ord a) => t a -> Maybe a
foldMin = getMin . foldMap (Min . Just)
于 2018-11-19T18:51:19.640 回答