haskell - 如何映射申请表？

Question

我想映射到 Applicative 表单。

类地图函数的类型如下：

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 表示向量数组 (x,y,z)。X, va 分别是位置、速度和加速度的数组。

定义 a 时会出现在 Applicative 形式上的映射。

---

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

毕竟，我的问题是“如何将高阶函数（如 map :: (a -> b) -> [a] -> [b]）提升到 Applicative 世界？​​” 我找到的答案是“使用提升的一阶函数来构建它们”。

例如，“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]，没有通用的方法可以把它变成[f a]——所以不需要 type 的函数f a -> f b。为了理智起见，我们将该函数简化为a -> f b（将其转换为另一个函数是微不足道的，但f前提是它是一个 monad）。

所以现在我们想要：

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

现在立即想到的是traversemapM 的泛化。Traverse，专门用于列表：

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

关闭，但没有雪茄。同样，我们可以将遍历提升到所需的类型签名，但这需要一个 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 = ...

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

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

Answer 2

如果我正在考虑这个问题，那么您不能仅使用应用函子来做到这一点；你需要一个单子。如果你有一个-Applicative调用它f- 你可以使用以下三个功能：

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

那么，给定一些f :: f a -> f b，你能用它做什么呢？好吧，如果您有一些xs :: [a]，那么您可以将其映射到：map (f . pure) xs :: [f b]。如果你改为拥有fxs :: f [a]，那么你可以改为这样做fmap (map (f . pure)) fxs :: f [f b]。¹ 然而，你被困在了这一点上。你想要一些类型[f b] -> f [b]的函数，可能还有类型的函数f (f b) -> f b；但是，您不能在应用函子上定义这些（编辑：实际上，您可以定义前者；参见编辑）。为什么？好吧，如果您查看fmap,pure和<*>，您会发现您无法摆脱（或重新排列）f类型构造函数，所以一旦您拥有[f a]，您就会陷入这种形式。

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

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

虽然join仅在 Control.Monad 中定义，但它与 一样基本>>=，有时可以更清晰地思考。 现在我们可以定义你的[m b] -> m [b]函数，或者你的m (m b) -> 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 -> m b) -> [a] -> m [b]，相当于mapM f = sequence . map f; 和(=<<) :: (a -> m b) -> m a -> 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 :: (Applicative f, Traversable t) => t (f a) => f (t a)；并且因为[]是 的一个实例Traversable，所以您可以对应用函子进行排序。尽管如此，您的类型签名仍然需要joinor =<<，所以您仍然卡住了。我可能会建议重新考虑您的设计；我认为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会更频繁地工作）。

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

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