如何映射申请表格？

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分别是位置,速度和加速度的数组.

定义一个适用的形式来定义一个.

---

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

毕竟,我的问题是"如何将高阶函数(如map ::(a - > b) - > [a] - > [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],没有通用的方法将其转换为[f a]- 因此不需要类型的函数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).如果你需要限制自己使用applicative,那么这应该足以说明你提出签名的原因是不可能的.

编辑:基于进一步的信息,这是我如何开始解决潜在的问题.

-- 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),那么你已经有了一个闭环,并且你的公式不propertly决定-无论是有,甚至给定的初始条件下,无限多的解决方案,或者根本不存在解决方案.

Answer 2

如果我正在考虑这个问题,那么你就不能只使用一个应用程序; 你需要一个monad.如果您有一个Applicative-call它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; 但是,你不能在applicative functors上定义它们(编辑:实际上,你可以定义前者;参见编辑).为什么？好吧,如果你看一下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,你可以定义你的mapXas

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,你可以对一个applicative functor 进行排序.然而,你的类型签名仍然需要join或=<<,所以你仍然卡住了.我可能会建议重新考虑你的设计; 我认为sclv可能有正确的想法.

1:或者map (f . pure) <$> fxs,使用Control.Applicative 的<$>同义词fmap.