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.

Beagle

Well, if you squint a bit then any Foldable will necessarily look like a list. – Occasionally

@leftaroundabout, that isn't quite true, since a Foldable could extend indefinitely in both directions. But I'm interested in the underlying intuition. It seems mostly to have to do with the ability to directly fold over the thing without anything else happening in between, but that's not really very formal. – Beagle

What about things like data Prod1 f g a = P1 (f a) (g a); newtype Comp f g a = Comp (f (g a)); data Sum1 f g a = L1 (f a) | R1 (g a)? These all have an instance (Foldable f, Foldable g) => Foldable (X f g); I would consider these non trivial. (I believe but haven't checked they all have law-abiding instances). – Disafforest

@user2407038, I don't see how you could build anything out of those that doesn't look like a container. – Beagle

Building on the answer of Daniel Wagner, you can write StateT as newtype StateT s m a = St { runSt :: (((->) s) :.: m :.: ((,) s)) a }, where :.: is Comp. If you agree that StateT is a non trivial Foldable, then you can indeed build a non-trivial Foldable from these. This relies on the Finite a => Foldable ((->) a) to qualify as a "non-trivial" Foldable, which will also looks like a container, if you squint hard enough (for example (->) Natural could be a representation of a list). I think the answer is based mainly on how you define 'container'. – Disafforest

Well anything can have a Foldable instance with toList x = []. I don't know what you mean by "non-trivial"; if you try to formalize it you may find that it is that condition which forces your functor to be "container-like". Traversable is a lot more interesting. – Loring

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.

Inexpugnable

Why does the first argument to ShapeSize have kind *->* when it is used only as f ()? Is the reason for that missing from the pseudo-translation to Haskell? Also, Haskell isn't so fussy about finiteness, allowing things like Traversable [] and Traversable Tree. How does that affect things? – Beagle

(a) The first argument to ShapeSize is in * -> * because so is the argument of Traversable that's being modelled; (b) Traversable doesn't make sense (undefined is a form of nonsense) for infinite structures, but it is common and inevitable Haskeller hypocrisy to pretend we mean just the finite fragment of an infinite type whenever it suits us, e.g. Eq instances. If ever we did separate data and codata, only the data would be Traversable. – Inexpugnable

On the other hand, one abomination (infinite traversable) mixes with another (lazy state) to produce perfectly sensible mapAccumL and mapAccumR for infinite structures. – Beagle

But perhaps the perfectly sensible things also admit perfectly sensible constructions. – Inexpugnable

In your lectures extension of a Normal is not the part of the definition of Normal, and Foldable then is isomorphic to Normal, sincenormalT is defined via sizeT, which is defined via crush, which is foldMap. (Whilst extension of a Normal is not isomorphic to Foldable, since there is no fmap). So what definition of Normal is pedantically precise? – Saurian

@user3237465 crush is only foldMapDefault for Traversable; my lecture notes say nothing about Foldable. You are kicking up dust which isn't there. – Inexpugnable

Sure, I just mean that if Foldable would be there, then every Foldable would give raise to a Normal (I said "isomorphic", but that was wrong — two definitions of Normal messed up in my head). – Saurian

@user3237465, what lectures are you referring to? Also, the link in your last comment is broken. – Beagle

@dfeuer, SSGEP-DataData ones. Here is a working link. – Saurian

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?

Orangeade

I think by then you have a container, and those instances sound sensible. – Beagle

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.

Kosygin