如何映射Applicative形式？

Question

我想映射应用形式。

类地图函数的类型如下：

mapX :: (Applicative f) => (f a -> f b) -> f [a] -> f [b]

用作：

result :: (Applicative f) => f [b]
result = mapX f xs
  where f  :: f a -> f b
        f = ...
        xs :: f[a]
        xs = ...

作为本文的背景，我尝试参考 Paul Haduk 的“The Haskell School of Expression”，使用 Applicative 风格编写流体模拟程序，我想表达Applicative 风格的模拟如下：

x, v, a :: Sim VArray
x = x0 +: integral (v * dt)
v = v0 +: integral (a * dt)
a = (...calculate acceleration with x v...)

instance Applicative Sim where
  ...

其中 Sim 类型表示模拟计算的过程，VArray 表示 Vector (x,y,z) 数组。 X、va 分别是位置、速度和加速度的数组。

定义 a 时就会映射到 Applicative 形式。

---

我找到了我的问题的一个答案。

毕竟，我的问题是“如何提升高阶函数（例如地图 ::(a->b)->; [一]-> [b]）到应用世界？”和答案 我发现是“使用提升的一阶函数来构建它们”。

例如，“mapX”是用提升的一阶函数定义的 (headA, tailA, consA, nullA, condA) 如下：

mapX :: (f a -> f b) -> f [a] -> f [b]
mapX f xs0 = condA (nullA xs0) (pure []) (consA (f x) (mapA f xs))
 where
   x = headA xs0
   xs = tailA xs0

headA = liftA head

tailA = liftA tail

consA = liftA2 (:)

nullA = liftA null

condA b t e = liftA3 aux b t e
  where aux b t e = if b then t else e

Answer 1

首先，我认为您提出的类型签名没有多大意义。给定一个应用列表 f [a] ，没有通用方法将其转换为 [fa] ——因此不需要 fa 类型的函数 -> ; f b 。为了保持理智，我们将该函数简化为 a ->; f b （将其转换为另一个是微不足道的，但前提是 f 是一个 monad）。

所以现在我们想要：

mapX :: (Applicative f) => (a -> f b) -> f [a] -> f [b]

现在立即想到的是traverse，它是mapM的泛化。遍历，专门用于列表：

traverse :: (Applicative f) => (a -> f b) -> [a] -> f [b]

关闭，但没有雪茄。同样，我们可以将 traverse 提升到所需的类型签名，但这需要一个 monad 约束：mapX f xs = xs >>= traverse f。

如果您不介意 monad 约束，这很好（事实上您可以使用 mapM 更直接地做到这一点）。如果您需要将自己限制在应用范围内，那么这应该足以说明为什么您提议的签名实际上不可能。

编辑：根据进一步的信息，我将如何开始解决根本问题。

-- your sketch
a = liftA sum $ mapX aux $ liftA2 neighbors (x!i) nbr 
   where aux :: f Int -> f Vector3
   -- the type of "liftA2 neighbors (x!i) nbr" is "f [Int]

-- my interpretation
a = liftA2 aux x v
    where
       aux :: VArray -> VArray -> VArray 
       aux xi vi = ...

如果你不能像那样写 aux —— 作为从某个时间点的位置和速度到加速度的纯函数，那么你就会遇到更大的问题......

这是一个关于原因的直观草图。流应用函子接受一个值，并随着时间的推移将其提升为一个值——一个值序列或值流。如果您可以随时间访问某个值，则可以派生它的属性。因此，速度可以用加速度来定义，位置可以用速度来定义，等等。伟大的！但现在您想根据位置和速度来定义加速度。也很棒！但在这种情况下，您不应该需要根据随时间变化的速度来定义加速度。你可能会问为什么？因为随时间变化的速度是加速度的开始。因此，如果您根据 dv 定义 a，并根据 integral(a) 定义 v，那么您'已经有一个闭环，并且您的方程没有正确确定 - 即使给定初始条件，也有无限多个解，或者根本没有解。

Answer 2

如果我的想法是正确的，那么你不能仅使用应用函子来做到这一点；你需要一个单子。如果您有一个 Applicative（称之为 f），您可以使用以下三个函数：

fmap  :: (a -> b) -> f a -> f b
pure  :: a -> f a
(<*>) :: f (a -> b) -> f a -> f b

因此，给定一些 f :: fa ->; f b，你能用它做什么？好吧，如果您有一些 xs :: [a]，那么您可以将其映射到：map (f .pure) xs :: [fb]。如果您有 fxs :: f [a]，那么您可以改为 fmap (map (f . pure)) fxs :: f [fb]。< support>1 但是，您现在陷入了困境。您想要一些 [fb] -> 类型的函数f [b]，并且可能是 f (fb) -> 类型的函数f b ；但是，您无法在应用函子上定义这些（编辑：实际上，您可以定义前者；请参阅编辑）。为什么？好吧，如果你看看 fmap、pure 和 <*>，你会发现你没有办法摆脱的（或重新排列）f类型构造函数，所以一旦你有了[fa]，你就会陷入这种形式。

幸运的是，这就是 monad 的用途：可以说，可以“改变形状”的计算。如果您有一个 monad m，那么除了上述之外，您还可以获得两个额外的方法（以及 return 作为 pure 的同义词）：

(>>=) :: m a -> (a -> m b) -> m b
join  :: m (m a) -> m a

虽然 join 仅在 Control.Monad 中定义，但它与 >>= 一样基本，有时可以更清晰地思考。 现在我们可以定义您的[mb] -> m [b] 函数，或者你的 m (mb) -> m b。后一个只是join；前者是 sequence，来自前奏曲。因此，使用 monad m，您可以将 mapX 定义为

mapX :: Monad m => (m a -> m b) -> m [a] -> m [b]
mapX f mxs = mxs >>= sequence . map (f . return)

但是，这将是一种奇怪的定义方式。序言中还有一些关于 monad 的其他有用函数：mapM :: Monad m => (a→mb)→ [一]-> m [b]，相当于 mapM f = sequence 。地图f；和 (=<<) :: (a -> mb) ->妈-> m b，相当于flip (>>=)。使用这些，我可能会将 mapX 定义为

mapX :: Monad m => (m a -> m b) -> m [a] -> m [b]
mapX f mxs = mapM (f . return) =<< mxs

---

编辑： 实际上，我的错误：正如 John L 在评论中善意指出的那样，Data.Traversable （这是一个基础包）提供函数 sequenceA ::（适用f, 可遍历 t) => t (fa) => f (ta);由于 [] 是 Traversable 的实例，因此您可以对应用函子进行排序。尽管如此，您的类型签名仍然需要 join 或 =<<，因此您仍然陷入困境。我可能会建议重新考虑你的设计；我认为 sclv 可能有正确的想法。

---

1： 或 map (f . pure) <$> fxs，使用 Control.Applicative 中 fmap 的 <$> 同义词。

Answer 3

这是 ghci 中的一个会话，我在其中按照您想要的方式定义了 mapX。

Prelude> 
Prelude> import Control.Applicative
Prelude Control.Applicative> :t pure
pure :: Applicative f => a -> f a
Prelude Control.Applicative> :t (<*>)
(<*>) :: Applicative f => f (a -> b) -> f a -> f b
Prelude Control.Applicative> let mapX fun ma = pure fun <*> ma
Prelude Control.Applicative> :t mapX
mapX :: Applicative f => (a -> b) -> f a -> f b

不过，我必须补充一点，fmap 更好用，因为 Functor 的表现力不如 Applicative（这意味着使用 fmap code> 会更频繁地工作）。

Prelude> :t fmap
fmap :: Functor f => (a -> b) -> f a -> f b

编辑：
哦，您还有 mapX 的其他签名，无论如何，您可能指的是我建议的那个 (fmap)？