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

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函数的作用，以及它们与这些类型同义词的关系。

---

这里有一些额外的信息，以便您不必跳转到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的比较。

- illabout

---

根据某个属性获取最小项（arg），而不是元素本身。 - Willem Van Onsem

我几个月前也有同样的问题，但是很难找到好的例子。自那以后，haddock已经得到了改进(https://gitlab.haskell.org/ghc/ghc/-/merge_requests/2911, https://gitlab.haskell.org/ghc/ghc/-/merge_requests/2950)，但我相信它们还可以进一步改进。 - sjakobi

那些类型的同义词并不实用。如果 Arg 的文档不足，应该进行扩展。 - dfeuer

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来选择最大或最小的项，根据该项的某个属性进行比较，但仍保留原始项。

- Mark Seemann

---

我之前在实际代码中使用过这个方法。我们想要实现一个类似于分配器的东西，使得将空间块添加回池中并从池中获取最大的空间块变得容易（但是还有更多关于块的信息我们希望在比较中忽略）。我们使用了一个现有的堆实现，并使用 ArgMax。完成了。另一种看待它的方式是：本质上它是装饰-排序-去装饰模式，但是针对的是最小值/最大值而不是排序。 - Daniel Wagner

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

虽然这种实现看起来有些复杂，但使用像幺半群这样的通用概念来实现事物通常是有帮助的。例如，在这种情况下，很容易通过一次遍历来适应上述代码以计算最小值和最大值。

- oisdk

Answer 3

我在以下情况下使用ArgMin / ArgMax：

• 我想要根据比较函数计算（一些值的）最小值/最大值。

• 比较功能开销大或难以重新计算，因此我想要缓存其结果；和/或

• 我想要使用foldMap进行单调操作，而不是使用显式/专门的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约束。这里的时间签名只是为了清晰起见。

- Jon Purdy