Single-pass folding of multiple structures.

FoldableN.hs

module Data.FoldableN where

import Control.Applicative -- for ZipList
import Linear.V1 -- for V1, an identity functor
import Linear.V2 -- for V2, data V2 a = V2 a a

class Foldable t => FoldableN t where
  -- | Fold multiple structures into a 'Monoid'.
  --
  -- @
  -- foldMap2 f a b = fold (liftA2 f a b)
  -- @
  foldMap2 :: Monoid m => (a -> b -> m) -> t a -> t b -> m

-- | we can fold identity functors
instance FoldableN V1 where
  foldMap2 f (V1 a) (V1 b) = f a b

-- | we can fold products with multiple fields of the parameter type
instance FoldableN V2 where
  foldMap2 f (V2 ax ay) (V2 bx by) = f ax bx <> f ay by

-- | we can ignore extra structure in products
instance FoldableN ((,) a) where
  foldMap2 f (_, a) (_, b) = f a b

-- | we can combine sums multiplicatively
instance FoldableN Maybe where
  foldMap2 f (Just a) (Just b) = f a b
  foldMap2 _ _        _        = mempty

-- | we have two possible instances for lists, corresponding to the 'Applicative' instances for [] and 'ZipList'
instance FoldableN [] where
  foldMap2 f (x:xs) ys = foldMap (f x) ys <> foldMap2 f xs ys
  foldMap2 _ _      _  = mempty

-- | I don’t know whether to expect that this is more useful than the other one or not
instance FoldableN ZipList where
  foldMap2 f (ZipList (x:xs)) (ZipList (y:ys)) = f x y <> foldMap2 f (ZipList xs) (ZipList ys)
  foldMap2 _ _                _                = mempty

Open question: does foldMap2 suffice to define foldMap3, foldMap4, etc., in the same manner as liftA2 suffices to define liftA3, liftA4, etc.?

Open question: does foldMap2 suffice to define foldMap3, foldMap4, etc., in the same manner as liftA2 suffices to define liftA3, liftA4, etc.?

It does indeed:

foldMap3 :: (FoldableN t, Monoid m) => (a -> b -> c -> m) -> t a -> t b -> t c -> m
foldMap3 f a b = foldMap (foldMap2 f a b)

One can also define foldMap2 with only foldMap!

foldMap2 :: (Foldable t, Monoid m) => (a -> b -> m) -> t a -> t b -> m
foldMap2 f a b = foldMap (foldMap f a) b

To define traverse2, however, one additionally needs a Monad instance for t:

traverse2 :: (Monad t, Traversable t, Applicative f) => (a -> b -> f c) -> t a -> t b -> f (t c)
traverse2 f a b = join <$> traverse (for b . f) a

@snowleopard points out that an Applicative instance suffices:

traverse2 :: (Applicative t, Traversable t, Applicative f) => (a -> b -> f c) -> t a -> t b -> f (t c)
traverse2 f a b = traverse (uncurry f) (liftA2 (,) a b)

This is, in fact, precisely the desired semantics—see for example the law given for foldMap2, above.