{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreiakascjzyw2wuxmapgy3mik2g6xgaf2qhwa3k6vfirjplnytnaofe",
    "uri": "at://did:plc:pi6woz4d47bkuws673w2il2r/app.bsky.feed.post/3mmpdx2cg4g52"
  },
  "path": "/t/lazily-consuming-a-self-referential-linked-list/14131#post_17",
  "publishedAt": "2026-05-25T19:48:42.000Z",
  "site": "https://discourse.haskell.org",
  "tags": [
    "what (co-)algebras are",
    "Here",
    "Programming with Bananas Lenses Envelopes and Barbed\nWire"
  ],
  "textContent": "VegOwOtenks:\n\n> Thanks for all the fancy words, made me look up and learn what (co-)algebras are.\n\nYou’re welcome  I wasn’t sure if you were aware of them or not. Sorry for the dictionary shock.\n\nVegOwOtenks:\n\n> what is a monadic anamorphism\n\nI’ll explain an anamorphism first and then I will explain a monadic\nanamorphism. An anamorphism is a combinator for constructing recursive\nfunctions that construct/build recursive data structures.\n\n\n    -- | Given any functor construct it's recursive form.\n    data Fix f = Fix (f (Fix f))\n\n    -- | Given a co-algebra construct a function that produces a recursive data structure.\n    ana :: (Functor f) => (a -> f a) -> a -> Fix f\n    ana coalg = let c = Fix . fmap c . coalg in c\n\n\nOne provides a co-algebra (which is typically non-recursive) to an\nanamorphism and the anamorphism provides a function that creates the\nrecursive data structure. Technically however, the functor that’s in\nuse corresponds to a class of recursive data structures. And that’s what\nthe `Recursive/CoRecursive` type classes and the `Base` type family are\nfor. I don’t have room to explain that here. So instead of using `Fix f`\nas the co-domain (return type) of the function we can use a more concrete\ndata structure like `[e]`.\n\nThe functor `f` above describes the structure of a single layer of\nrecursion (when to terminate, and when to keep going, what data to\nremember at each layer etc). The purpose of the anamorphism is then to\nproduce the fully recursive function `a -> Fix f`. Here’s a concrete\nexample:\n\n\n    data ListF e a = Nil | Cons e a\n      deriving (Functor f)\n\n    nSized :: Natural -> ListF Natural Natural\n    nSized 0 = Nil\n    nSized n = Cons n (n-1)\n\n    -- Fix (ListF e) ~ [e]\n    sizedList :: Natural -> [Natural]\n    sizedList = ana evens\n\n\nMonadic anamorphisms are anamorphisms that operate over a monad. More\nconcretely their co-domain is wrapped in a monad `m` - in both the\nco-algebra and the return type:\n\n\n    ana  :: (Functor f)          => (a ->    f a)  -> a ->    Fix f\n    anaM :: (Monad m, Functor f) => (a -> m (f a)) -> a -> m (Fix f)\n\n\nNow let’s say that you want to write a program where the user gives your\nprogram `n` names to consume via CLI prompts. You’ll need a way ask\nthe user for a value as noted by `askforName`. Now let’s say we will\nkeep asking the user for values until they type “done”. We’ll need to\nrecursively ask for a name, check if the given string is equivalent to\n“done” and then based on the resulting truth value we terminate or\nwe recurse.\n\nWe can use a monadic anamorphism to accomplish this. I’ll write the proof steps below:\n\n\n    import Data.Functor ((<&>))\n\n    -- If IO throws exceptions we won't handle them here.\n    askForName :: IO String\n    askForName = do\n      putStrLn \"Next name please:\"\n      getLine\n\n    -- Claim: allNames can be defined using a monadic anamorphism\n    allNames  :: IO [String] -- we want to construct this\n      {- forall a. a ~ () -> a -}\n      -- :: () -> IO [String]\n      {- exists f. Base t ~ f. t ~ Fix f -}\n      -- :: () -> IO (Fix (ListF String))\n    allNames = anaM nextName ()\n\n    nextName :: () -> IO (ListF String ())\n    nextName _ = askForName <&> \\case\n      -- we're done, terminate\n      \"done\" -> Nil\n      -- assume the user typed a valid name...\n      name   -> Cons name ()\n\n\nThe benefit of `nextName` is that it’s non-recursive. The `ListF`\nfunctor completely determines the structure of the recursion and when we\nterminate becomes very clear. Unfortunately this example doesn’t show\ncase the full power of recursion schemes, however I’ve written many a\nserver streaming handler with them with robust error handling and you\ncan imagine the recursion gets very tricky. Recursion schemes solves\nmany of these problems.\n\nI believe a lot of mistakes in Haskell can be avoided by writing\nrecursion-schemes instead of explicit recursion. If you’re interested\nin learning more:\n\n  * Here is a great resource to learn more about recursion schemes.\n  * I _highly_ recommend reading the\nProgramming with Bananas Lenses Envelopes and Barbed\nWire\nfunctional perl. It can be overwhelming at first but if you have the\ntime and energy to wade through it you’ll be a changed programmer (for\nexample you’ll begin to spot easy ways to refactor your code and create\noptimizations algebraically).\n\n\n\nI will post another response after I did int your code a bit more.",
  "title": "Lazily consuming a self-referential linked list"
}