Data.Semigroup 中 ArgMin 和 ArgMax 类型同义词的用途是什么？

Question

base library in Haskell has the following type synonyms in Data.Semigroup:

type ArgMin a b = Min (Arg a b)

type ArgMax a b = Max (Arg a b)

这里是黑线鳕的链接：ArgMin and ArgMax

这两种同义词的作用是什么？在哪里可以有效使用它们？

解释 argmin 和 argmax 函数在数学中的作用，以及它与这些类型同义词的关系，可能会有所帮助。

这里有一些额外的信息，因此您不必跳转到 Hackage。

这里是Arg的定义：

-- | 'Arg' isn't itself a 'Semigroup' in its own right, but it can be
-- placed inside 'Min' and 'Max' to compute an arg min or arg max.
data Arg a b = Arg a b

它的文档字符串建议 ArgMin 和 ArgMax 可以放在 Min 和 Max 的内部来计算 arg min 或 arg max。

Min 和 Max 如下所示：

newtype Min a = Min { getMin :: a }

Semigroup 实例很有趣：

instance Ord a => Semigroup (Min a) where
  (<>) = coerce (min :: a -> a -> a)

它看起来像在使用 min 作为 (<>)。

我们可以看看 Arg 的 Ord 实例是什么样的，因为它与此处相关：

instance Ord a => Ord (Arg a b) where
  Arg a _ `compare` Arg b _ = compare a b
  min x@(Arg a _) y@(Arg b _)
    | a <= b    = x
    | otherwise = y
  max x@(Arg a _) y@(Arg b _)
    | a >= b    = x
    | otherwise = y

这似乎仅运行第一个类型参数与 Arg 的比较。

Answer 1

我想这是 Haskell 中存在的那些东西之一，因为存在理论概念。我不确定这些类型是否有很多实际用途，但它们确实说明了半群和幺半群的概念在编程方面有多么广泛。

想象一下，例如，您需要选择两个名字中最长的一个，name1 和 name2，它们都是 String 值。您可以为此使用 ArgMax 的 Semigroup 实例：

Prelude Data.Semigroup> Max (Arg (length name1) name1) <> Max (Arg (length name2) name2)
Max {getMax = Arg 5 "Alice"}

之后，就是从容器中解包 "Alice" 的问题了。

正如 Willem Van Onsem 在评论中指出的那样，您可以根据项目的某些属性使用 ArgMax 和 ArgMin 来选择最大或最小项目，但仍保持原始状态项目周围。

Answer 2

它们的目的是实现 minimumOn:

minimumOn :: (Ord b, Foldable f) => (a -> b) -> f a -> Maybe a
minimumOn f = fmap (getArg  . getMin)
            . getOption
            . foldMap (Option . Just . Min . (Arg =<< f))
            --                         ^^^^^^^^^^
            --                           ArgMin
  where
    getArg (Arg _ x) = x

虽然此实现可能看起来有点复杂，但使用幺半群等一般概念来实现通常很有帮助。例如，在这种情况下，直接修改上面的代码以在一次通过中计算最小值和最大值。

Answer 3

我达到 ArgMin / ArgMax 时：

我想根据比较函数
计算一些值的minimum/maximum的（函数）
比较昂贵或笨拙重新计算，所以我想缓存它的结果； and/or
我想用 foldMap 而不是 explicit/specialised minimumBy / maximumBy 或 sortOn让它灵活地适应未来的变化，例如不同的幺半群或并行化

这是对我工作中最近的一个真实示例的改编，findNextWorkerQueue，它获取从工人到任务的映射，并找到最早完成第一项任务的工人，例如鉴于此输入：

工人 1:
- 时间 10：任务 A
- 时间 12：任务 B
- 时间 14：任务 C
工人 2：
- 时间 5：任务 D
- 时间 10：任务 E
- 时间 15：任务 F
工人 3：
- 时间 22：任务 G
- 时间 44：任务 H

它将产生一个开始时间 5 和一个描述工人 2 的工作队列，第一个任务是 D，后续任务是 E & F。

{-# LANGUAGE ScopedTypeVariables #-}

import Data.Map       (Map)
import Data.Semigroup (Arg(..), Min(..), Option(..))
import Data.Sequence  (Seq(Empty, (:<|)))

import qualified Data.Map as Map

-- An enumeration of computation units for running tasks.
data WorkerId = …

-- The timestamp at which a task runs.
type Time = Int

-- Some kind of task scheduled at a timestamp.
data Scheduled task = Scheduled
  { schedAt   :: !Time
  , schedItem :: !task
  }

-- A non-empty sequence of work assigned to a worker.
data WorkQueue task = WorkQueue
  { wqId    :: !WorkerId
  , wqFirst :: !(Scheduled task)
  , wqRest  :: !(Seq (Scheduled task))
  }

-- | Find the lowest worker ID with the first scheduled task,
-- if any, and return its scheduled time and work queue.
findNextWorkerQueue
  :: forall task
  .  Map WorkerId (Seq (Scheduled task))
  -> Maybe (Time, WorkerQueue task)
findNextWorkerQueue
  = fmap getTimeAndQueue . getOption
  . foldMap (uncurry minWorkerTask) . Map.assocs
  where

    minWorkerTask
      :: WorkerId
      -> Seq (Scheduled task)
      -> Option (Min (Arg (Time, WorkerId) (WorkQueue task)))
    minWorkerTask wid tasks = Option $ case tasks of
      Empty -> Nothing
      t :<| ts -> Just $ Min $ Arg
        (schedTime t, wid)
        WorkQueue { wqId = wid, wqFirst = t, wqRest = ts }

    getTimeAndQueue
      :: Min (Arg (Time, WorkerId) (WorkQueue task))
      -> (Time, WorkQueue task)
    getTimeAndQueue (Min (Arg (time, _) queue))
      = (time, queue)

（请注意，这是使用 Option 来支持 GHC 8.6；在 GHC ≥8.8 中，Maybe 有一个改进的 Monoid 实例取决于 Semigroup 而不是 Monoid，因此我们可以将它与 Min 一起使用，而无需施加 Bounded 约束。拍号只是为了清楚起见。）

Data.Semigroup 中 ArgMin 和 ArgMax 类型同义词的用途是什么？

What is the purpose of the ArgMin and ArgMax type synonyms in Data.Semigroup?

haskell

monoids

argmax

semigroup

type-synonyms