Haskell Language Traversable Traversable structures as shapes with contents
Example
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)
