Free-like data structure:

ashokkimmel:

data Traversal' a b x t
    = End x t
    | Step (Traversal' a b (a,x) (b -> t)) deriving Functor

The way I thought of it was this.

data Free0   f    a    = Pure0    a     | Free0 (Free0   f    (f a))         -- Original Free
data Free1 g f    a    = Pure1 (g a)    | Free1 (Free1 g f    (f a))         -- Compose with another functor
data Free2 g f f' a a' = Pure2 (g a a') | Free2 (Free2 g f f' (f a) (f' a')) -- Add another type parameter
type Traversal' a b x t = Free2 (,) ((,) a) ((->) b) x t

I thought Free2 and Free were very similar, and the Traversal' defined above could be implemented as a special case of Free2.