8

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)

看起来它正在使用minas (<>)。

我们可以看看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。

4

3 回答 3

5

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

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

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

之后，这只是"Alice"从容器中打开包装的问题。

正如 Willem Van Onsem 在评论中指出的那样，您可以根据项目的某些属性使用ArgMaxandArgMin选择最大或最小项目，但仍保留原始项目。

于 2020-11-20T13:42:52.870 回答
3

它们的目的是实现以下内容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 这样的一般概念来实现通常很有帮助。例如，在这种情况下，可以直接修改上面的代码来一次计算最小值和最大值。

于 2020-11-20T20:27:32.903 回答
2

我伸手去拿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使用它。时间签名在这里只是为了清楚起见。）MinBounded

于 2020-11-20T22:22:33.553 回答