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

Question

Haskell中的base库在Data.Semigroup中有以下同义词

type ArgMin a b = Min (Arg a b)

type ArgMax a b = Max (Arg a b) 

下面是指向哈德克的链接：ArgMin和ArgMax

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

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

这里有一些额外的信息，这样你就不必跳槽了。

以下是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

它的doc字符串表明，ArgMin和ArgMax可以放置在Min和Max中，以计算arg或arg。

Min和Max看起来如下所示：

newtype Min a = Min { getMin :: a }

Semigroup实例很有趣：

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

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

我们可以查看Ord实例对于Arg的外观，因为它在这里是相关的：

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的ArgMax实例：

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

虽然这个实现看起来有点复杂，但是使用诸如monoids之类的一般概念来实现东西通常是很有帮助的。例如，在这种情况下，简单地修改上面的代码，在一次传递中计算min和max。

Answer 3

我到达ArgMin / ArgMax时：

• I希望根据比较函数

计算某些值的最小/最大值。

• 比较昂贵或难以重新计算，所以我想缓存它的结果；和/或

我想用parallelisation，而不是一个显式的/专门的minimumBy / maximumBy或sortOn，让它灵活地适应未来的变化，比如一个不同的单样体或

• 。

下面是我工作中最近的一个现实世界的例子，findNextWorkerQueue，它将一张从工人到任务的地图，找到了最早的第一个任务，例如，给定这个输入：

• Worker 1:

- Time 10: Task A
- Time 12: Task B
- Time 14: Task C

• Worker 2:

- Time 5: Task D
- Time 10: Task E
- Time 15: Task F

• Worker 3:

- Time 22: Task G
- Time 44: Task 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来支持GHC8.6；在GHC≥8.8中，Maybe有一个改进的Monoid实例，依赖于Semigroup而不是Monoid，因此我们可以将它与Min一起使用，而无需施加Bounded约束。时间签名只是为了清晰起见。)