Haskell Language Traversable structures as shapes with contents


If a type t is Traversable then values of t a can be split into two pieces: their "shape" and their "contents":

data Traversed t a = Traversed { shape :: t (), contents :: [a] }

where the "contents" are the same as what you'd "visit" using a Foldable instance.

Going one direction, from t a to Traversed t a doesn't require anything but Functor and Foldable

break :: (Functor t, Foldable t) => t a -> Traversed t a 
break ta = Traversed (fmap (const ()) ta) (toList ta)

but going back uses the traverse function crucially

import Control.Monad.State

-- invariant: state is non-empty
pop :: State [a] a
pop = state $ \(a:as) -> (a, as)

recombine :: Traversable t => Traversed t a -> t a
recombine (Traversed s c) = evalState (traverse (const pop) s) c

The Traversable laws require that break . recombine and recombine . break are both identity. Notably, this means that there are exactly the right number elements in contents to fill shape completely with no left-overs.

Traversed t is Traversable itself. The implementation of traverse works by visiting the elements using the list's instance of Traversable and then reattaching the inert shape to the result.

instance Traversable (Traversed t) where
    traverse f (Traversed s c) = fmap (Traversed s) (traverse f c)