Is there an efficient, lazy way to fuse foldMap with traverse?

Question

A recent proposal on the Haskell libraries mailing list led me to consider the following:

ft :: (Applicative f, Monoid m, Traversable t)
   -> (b -> m) -> (a -> f b) -> t a -> f m
ft f g xs = foldMap f <$> traverse g xs

I noticed that the Traversable constraint can be weakened to Foldable:

import Data.Monoid (Ap (..))  -- Requires a recent base version

ft :: (Applicative f, Monoid m, Foldable t)
   -> (b -> m) -> (a -> f b) -> t a -> f m
ft f g = getAp . foldMap (Ap . fmap f . g)

In the original proposal, f was supposed to be id, leading to

foldMapA
  :: (Applicative f, Monoid m, Foldable t)
   -> (a -> f m) -> t a -> f m
--foldMapA g = getAp . foldMap (Ap . fmap id . g)
foldMapA g = getAp . foldMap (Ap . g)

which is strictly better than the traverse-then-fold approach.

But in the more general ft, there's a potential problem: fmap could be expensive in the f functor, in which case the fused version could potentially be more expensive than the original!

The usual tools for dealing with expensive fmap are Yoneda and Coyoneda. Since we need to lift many times and only lower once, Coyoneda is the one that can help us:

import Data.Functor.Coyoneda

ft' :: (Applicative f, Monoid m, Foldable t)
    => (b -> m) -> (a -> f b) -> t a -> f m
ft' f g = lowerCoyoneda . getAp
  . foldMap (Ap . fmap f . liftCoyoneda . g)

So now we replace all those expensive fmaps with one (buried in lowerCoyoneda). Problem solved? Not quite.

The trouble with Coyoneda is that its liftA2 is strict. So if we write something like

import Data.Monoid (First (..))

ft' (First . Just) Identity $ 1 : undefined
-- or, importing Data.Functor.Reverse,
ft' (Last . Just) Identity (Reverse $ 1 : undefined)

then it will fail, whereas ft has no trouble with those. Is there a way to have our cake and eat it too? That is, a version that uses only a Foldable constraint, only fmaps O(1) times more than traverse in the f functor, and is just as lazy as ft?

---

Note: we could make liftA2 for Coyoneda somewhat lazier:

liftA2 f m n = liftCoyoneda $
  case (m, n) of
    (Coyoneda g x, Coyoneda h y) -> liftA2 (\p q -> f (g p) (h q)) x y

This is enough to let it produce an answer to ft' (First . Just) Identity $ 1 : 2 : undefined, but not to ft' (First . Just) Identity $ 1 : undefined. I don't see any obvious way to make it lazier than that, because pattern matches on existentials must always be strict.

Answer 1

我不相信这是可能的。避免fmap在元素处使用 s 似乎需要对容器的结构有一定的了解。例如，Traversable列表的实例可以写成

traverse f (x : xs) = liftA2 (:) (f x) (traverse f xs)

我们知道 的第一个参数(:)是单个元素，因此我们可以将该liftA2元素的操作映射过程与将该操作的结果与列表其余部分关联的结果相结合的过程结合起来。

在更通用的上下文中，可以使用具有虚假实例的岩浆类型来忠实地捕获折叠结构Monoid：

data Magma a = Bin (Magma a) (Magma a) | Leaf a | Nil
  deriving (Functor, Foldable, Traversable)

instance Semigroup (Magma a) where
  (<>) = Bin
instance Monoid (Magma a) where
  mempty = Nil

toMagma :: Foldable t => t a -> Magma a
toMagma = foldMap Leaf

我们可以写

ft'' :: (Applicative f, Monoid m, Foldable t)
   => (b -> m) -> (a -> f b) -> t a -> f m
ft'' f g = fmap (lowerMagma f) . traverse g . toMagma

lowerMagma :: Monoid m => (a -> m) -> Magma a -> m
lowerMagma f (Bin x y) = lowerMagma f x <> lowerMagma f y
lowerMagma f (Leaf x) = f x
lowerMagma _ Nil = mempty

但实例中存在问题Traversable：

traverse f (Leaf x) = Leaf <$> f x

这正是我们试图避免的麻烦。而且没有办法解决这个问题。如果遇到Bin l r，我们无法懒惰地判断 或l是否r是叶子。所以我们被困住了。如果我们允许对Traversable进行约束，我们可以捕获使用更丰富的岩浆类型（例如 中使用的岩浆类型）遍历ft''的结果，我怀疑这可以让我们做一些更聪明的事情，尽管我还没有发现任何东西。lens