Are there non-trivial Foldable or Traversable instances that don't look like containers?

Question

There are lots of functors that look like containers (lists, sequences, maps, etc.), and many others that don't (state transformers, IO, parsers, etc.). I've not yet seen any non-trivial Foldable or Traversable instances that don't look like containers (at least if you squint a bit). Do any exist? If not, I'd love to get a better understanding of why they can't.

Answer 1

Every valid Traversable f is isomorphic to Normal s for some s :: Nat -> * where

data Normal (s :: Nat -> *) (x :: *) where  -- Normal is Girard's terminology
  (:-) :: s n -> Vec n x -> Normal s x

data Nat = Zero | Suc Nat

data Vec (n :: Nat) (x :: *) where
  Nil   :: Vec Zero n
  (:::) :: x -> Vec n x -> Vec (Suc n) x

but it's not at all trivial to implement the iso in Haskell (but it's worth a go with full dependent types). Morally, the s you pick is

data {- not really -} ShapeSize (f :: * -> *) (n :: Nat) where
  Sized :: pi (xs :: f ()) -> ShapeSize f (length xs)

and the two directions of the iso separate and recombine shape and contents. The shape of a thing is given just by fmap (const ()), and the key point is that the length of the shape of an f x is the length of the f x itself.

Vectors are traversable in the visit-each-once-left-to-right sense. Normals are traversable exactly in by preserving the shape (hence the size) and traversing the vector of elements. To be traversable is to have finitely many element positions arranged in a linear order: isomorphism to a normal functor exactly exposes the elements in their linear order. Correspondingly, every Traversable structure is a (finitary) container: they have a set of shapes-with-size and a corresponding notion of position given by the initial segment of the natural numbers strictly less than the size.

The Foldable things are also finitary and they keep things in an order (there is a sensible toList), but they are not guaranteed to be Functors, so they don't have such a crisp notion of shape. In that sense (the sense of "container" defined by my colleagues Abbott, Altenkirch and Ghani), they do not necessarily admit a shapes-and-positions characterization and are thus not containers. If you're lucky, some of them may be containers upto some quotient. Indeed Foldable exists to allow processing of structures like Set whose internal structure is intended to be a secret, and certainly depends on ordering information about the elements which is not necessarily respected by traversing operations. Exactly what constitutes a well behaved Foldable is rather a moot point, however: I won't quibble with the pragmatic benefits of that library design choice, but I could wish for a clearer specification.

Answer 2

Well, with the help of universe, one could potentially write Foldable and Traversable instances for state transformers over finite state spaces. The idea would be roughly similar to the Foldable and Traversable instances for functions: run the function everywhere for Foldable and make a lookup table for Traversable. Thus:

import Control.Monad.State
import Data.Map
import Data.Universe

-- e.g. `m ~ Identity` satisfies these constraints
instance (Finite s, Foldable m, Monad m) => Foldable (StateT s m) where
    foldMap f m = mconcat [foldMap f (evalStateT m s) | s <- universeF]

fromTable :: (Finite s, Ord s) => [m (a, s)] -> StateT s m a
fromTable vs = StateT (fromList (zip universeF vs) !)

float :: (Traversable m, Applicative f) => m (f a, s) -> f (m (a, s))
float = traverse (\(fa, s) -> fmap (\a -> (a, s)) fa)

instance (Finite s, Ord s, Traversable m, Monad m) => Traversable (StateT s m) where
    sequenceA m = fromTable <$> traverse (float . runStateT m) universeF

I'm not sure whether this makes sense. If it does, I think I would be happy to add it to the package; what do you think?

Answer 3

I don’t think it’s actually Foldable or Traversible, but MonadRandom is an example of something that could be, functioning like an infinite list, but which doesn't look any more like a container than anything else that’s foldable. Conceptually, it’s a random variable.