{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreiezw4tm6xaefgocstgn5pftsznaqkeat6znvwcib2qg3ha66ezcva",
    "uri": "at://did:plc:pi6woz4d47bkuws673w2il2r/app.bsky.feed.post/3mksjhv2djbm2"
  },
  "path": "/t/free-like-data-structure/14012#post_6",
  "publishedAt": "2026-05-01T14:12:28.000Z",
  "site": "https://discourse.haskell.org",
  "textContent": "I used a similar structure to make the free traversal. I think that `Traversal'` one defined here is within Haskell 1998 specification.\n\n\n    applyF :: Functor f => f (a -> b) -> a -> f b\n    applyF f x = fmap ($ x) f\n    data Traversal' a b x t\n        = End x t\n        | Step (Traversal' a b (a,x) (b -> t)) deriving Functor\n    instance Bifunctor (Traversal' a b) where\n        first f (End x t) = End (f x) t\n        first f (Step f') = Step $ first (fmap f) f'\n        bimap f g = first f . fmap g\n\n    getTraversal' :: Traversal' a b (a,x) t -> (a,Traversal' a b x t)\n    getTraversal' (End (a,b) c) =  (a, End b c)\n    getTraversal' (Step f) = case getTraversal' f of\n        (a,b) -> (a, Step b)\n\n    instance (x ~ ()) => Applicative (Traversal' a b x) where\n        pure x = End () x\n        End () f <*> c = fmap f c\n        Step   f <*> c = Step $ first (a,) ((flip <$> x) <*> c) where\n            (a,x) = getTraversal' f\n\n    type Traversal s t a b = s -> Traversal' a b () t\n    type TraversalR s t a b = forall f. Applicative f => (a -> f b) -> s -> f t\n\n    fromRank :: TraversalR s t a b -> Traversal s t a b\n    fromRank f s = f traversal s where\n        traversal :: a -> Traversal' a b () b\n        traversal a = Step $ End (a,()) id\n\n    withA :: forall f a b x t. Applicative f => (a -> f b) -> Traversal' a b x t -> f t\n    withA _ (End _ t) = pure t\n    withA f (Step tr) =\n        let (a, rest) = getTraversal' tr\n        in withA f rest <*> f a\n\n    toRank :: Traversal s t a b -> TraversalR s t a b\n    toRank f g s = withA g (f s)\n\n\nIt’s obviously really inneficient though, so it would be a poor substitute for the `RankNType` implementation of `Traversal` used by `optics`",
  "title": "Free-like data structure:"
}