您可以仅使用列表 monad 来确定列表的最小值或最大值吗？

Question

试图理解 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 块的范围内执行生成这样的汇总值的操作？

Answer 1

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

So it would not be possible to do an operation that produces a summary value like this within the confines of a do block?

正确，那是不可能的。 Haskell 的 do 符号是 Monad 的语法糖，所以基本上是 >>= 和 return.

的语法糖如您所知，

return 不允许您 'access' Monad 的内容，因此您只能通过 [=14= 访问您拥有的内容]，例如，在列表 monad 的情况下，它一次只给你一个值。

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

例如，您可以找到集合中的最小值：

Prelude Data.Foldable Set> foldr (\x -> Just . maybe x (min x)) Nothing $ Set.fromList [42, 1337, 90125, 2112]
Just 42

Answer 2

下面的人为设计和低效代码是我能得到的最接近 "using only the list monad" 的代码。这可能不是 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

Answer 3

我也不确定，实际问题是什么，但是可以使用 Monoid 实例隐藏对累加器的需求。然后 - 对于您的最小示例 - 您可以使用 Data.Foldable 中的 foldMap 来映射和合并 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)

您可以仅使用列表 monad 来确定列表的最小值或最大值吗？

Can you determine the min or max of a list using only the list monad?

monads

haskell

foldable