haskell - 如何实现这种 Traversable 使用模式？

Question

使用时Data.Traversable我经常需要一些代码，例如

import Control.Applicative (Applicative,(<*>),pure)
import Data.Traversable (Traversable,traverse,sequenceA)
import Control.Monad.State (state,runState)

traverseF :: Traversable t => ((a,s) -> (b,s)) -> (t a, s) -> (t b, s)
traverseF f (t,s) = runState (traverse (state.curry f) t) s

遍历结构并建立一个由某种状态驱动的新结构。我注意到类型签名模式并相信它可以概括为

fmapInner :: (Applicative f,Traversable t) => (f a -> f b) -> f (t a) -> f (t b)
fmapInner f t = ???

但我无法仅用traverse来实现这一点, sequenceA , fmap , <*>和pure 。也许我需要更强的类型类约束？我绝对需要 Monad在这里？

更新

具体来说，我想知道是否可以定义 fmapInner对于f适用于任何 Traversable t并且应用了一些直觉法则(我还不知道法则应该是什么)，这是否意味着 f事情是一个Monad ？因为，对于Monad实现很简单:

--Monad m implies Applicative m but we still 
--  have to say it unless we use mapM instead
fmapInner :: (Monad m,Traversable t) => (m a -> m b) -> m (t a) -> m (t b)
fmapInner f t = t >>= Data.Traversable.mapM (\a -> f (return a))

更新

感谢您的出色回答。我发现我的traverseF只是

import Data.Traversable (mapAccumL)
traverseF1 :: Traversable t => ((a, b) -> (a, c)) -> (a, t b) -> (a, t c)
traverseF1 =uncurry.mapAccumL.curry

不显式使用 Monad.State 并翻转所有对。以前我以为是mapAccumR但实际上是mapAccumL其工作原理类似于 traverseF .

Answer 1

我现在已经说服自己这是不可能的。这就是原因，

 tF ::(Applicative f, Traversable t) => (f a -> f b) -> f (t a) -> f (t b)

因此，我们有一个返回 t a 的副作用计算，我们希望用它来确定会发生什么副作用。换句话说，类型t a的值将决定当我们应用traverse时会发生什么副作用。

然而，这对于应用类型类来说是不可能的。我们可以动态选择值，但计算的副作用是静态的。明白我的意思，

pure :: a -> f a -- No side effects
(<*>) :: f (a -> b) -> f a -> f b -- The side effects of `f a` can't
                                  -- decide based on `f (a -> b)`.

现在有两种可能的方法可以根据先前的值确定副作用，

smash :: f (f a) -> f a

因为这样我们就可以简单地做到

smash $ (f :: a -> f a) <$> (fa :: f a) :: f a

现在你的函数变成了

traverseF f t = smash $ traverse (f . pure) <$> t

或者我们可以有

bind :: m a -> (a -> m b) -> m b -- and it's obvious how `a -> m b`
                                 -- can choose side effects.

和

traverseF f t = bind t (traverse $ f . pure)

但它们分别是 join 和 >>=，并且是 Monad 类型类的成员。所以是的，你需要一个单子(monad)。 :(

此外，带有 monad 约束的函数的一个很好的、无点实现是

traverseM = (=<<) . mapM . (.return)

编辑，

我认为值得注意的是

traverseF :: (Applicative f,Traversable t) => (f a -> f b) -> t a -> f (t a)
traverseF = traverse . (.pure)