Free-like data structure:

I used a similar structure to make the free traversal. I think that Traversal' one defined here is within Haskell 1998 specification.

applyF :: Functor f => f (a -> b) -> a -> f b
applyF f x = fmap ($ x) f
data Traversal' a b x t
    = End x t
    | Step (Traversal' a b (a,x) (b -> t)) deriving Functor
instance Bifunctor (Traversal' a b) where
    first f (End x t) = End (f x) t
    first f (Step f') = Step $ first (fmap f) f'
    bimap f g = first f . fmap g

getTraversal' :: Traversal' a b (a,x) t -> (a,Traversal' a b x t)
getTraversal' (End (a,b) c) =  (a, End b c)
getTraversal' (Step f) = case getTraversal' f of
    (a,b) -> (a, Step b)

instance (x ~ ()) => Applicative (Traversal' a b x) where
    pure x = End () x
    End () f <*> c = fmap f c
    Step   f <*> c = Step $ first (a,) ((flip <$> x) <*> c) where
        (a,x) = getTraversal' f

type Traversal s t a b = s -> Traversal' a b () t
type TraversalR s t a b = forall f. Applicative f => (a -> f b) -> s -> f t

fromRank :: TraversalR s t a b -> Traversal s t a b
fromRank f s = f traversal s where
    traversal :: a -> Traversal' a b () b
    traversal a = Step $ End (a,()) id

withA :: forall f a b x t. Applicative f => (a -> f b) -> Traversal' a b x t -> f t
withA _ (End _ t) = pure t
withA f (Step tr) =
    let (a, rest) = getTraversal' tr
    in withA f rest <*> f a

toRank :: Traversal s t a b -> TraversalR s t a b
toRank f g s = withA g (f s)

It’s obviously really inneficient though, so it would be a poor substitute for the RankNType implementation of Traversal used by optics