{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreihcpnkxtal2k3m4e2ibdlsdcyiqvb3evbeh3o7kuljprxmyei4rfi",
    "uri": "at://did:plc:pi6woz4d47bkuws673w2il2r/app.bsky.feed.post/3mfdn4x6p2ie2"
  },
  "path": "/t/improving-memory-with-better-abstractions/12350?page=2#post_29",
  "publishedAt": "2026-02-21T01:16:01.000Z",
  "site": "https://discourse.haskell.org",
  "tags": [
    "making class for packable Bitfields",
    "@TypeApplication",
    "@Byte",
    "@Bit"
  ],
  "textContent": "# Two classes diverged in a codebase\n\nTwo classes diverged in a code (base),\nAnd sorry I could not implement both\nAnd be one hierarchy, long I stood\nAnd fiddled with laws as far as I could\nTo where they forked in the undergrowth;\n\nThen look’d the other, more often used\nAnd having perhaps the better claim,\nBecause it was parametric content loose’d,\nThough as for that the mapping there\nHad worn them really about the same,\n\nAnd both that morning equally lay\nIn thunks no evaluator had trodden black.\nOh, I kept the first for another day!\nYet knowing how way leads on to way,\nI doubted if I should ever come back.\n\nI shall be telling this with a sigh\nSomewhere ages and ages hence:\nTwo classes diverged in a codebase, and I,\nI took neither and ran straight through the middle,\nAnd that has made all the difference.\n\n* * *\n\nThis poem is about MonoFunctor and Functor. I wanted to leverage one or the other as part of my attempts to improve the `Data.Bits` typeclass (it seems sensible right, container of bits?). However, they both proved to be insufficient, so I went through the middle.\n\n# Endofunctors\n\nMy inspiration is thus: I want to be able to map over bits and bytes. Haskell loves its functors - they are neato and powerful - but then I asked, “Well what if I cant change type during map?”. The problem is, things that are `Bits` are not usually actually `Functor`, because the `Bit` element is not parametric in eg `Word8`.\n\nEnter ‘MonoFunctor’ which just has `omap :: (Element mono -> Element mono) -> mono -> mono` where the content type is A) tied to the structure type and B) cannot be changed. It has many of the same problems / features that allocated memory has (and thus is also very similar to `MemFunctor` et al) so`MonoFunctor` sort of gives us what we need (hurrah) but it also kind of sucks because it restricts you to one implementation - eg, if your `Element a` is `Bit` , it cannot be `Byte` - and memory is both bits and bytes at the same time, so eg I need to be able to make `Word64` a monofunctor over `Bit` and over `Byte` at the same time.\n\nI need something in between; in other words, I need some sort of… poly- or multi- monomorphic functor - a polymonofunctor? This just didn’t sound good but then I thought of how Haskell `Functor` is really an endofunctor over `Hask`, and I knew what I needed to do.\n\nEnter `Endofunctor` ! Endo is much better characterization than polymono - it is both mathy and accurate (I hope)!\n\nThe core classes are:\n\n\n    class Endofunctor u mu where\n        endomap :: (u -> u) -> mu -> mu\n        endozip :: (u -> u -> u) -> mu -> mu -> mu\n\n    class Endofoldable u mu where\n        endofoldl :: (a -> u -> a) -> a -> mu -> a\n        endofoldr :: (u -> a -> a) -> a -> mu -> a\n        endofoldMap :: Monoid m => (u -> m) -> mu -> m\n\n    class (Endofunctor u mu, Endofoldable u mu) => Endotraversable u mu where\n        endotraverse :: (Applicative f) => (u -> f u) -> mu -> f mu\n\n    -- Ops here are still being workshopped, I didnt mention them all for brevity\n    class IndexedEndofunctor u mu where\n\n        -- A more efficient implementation for endomapAt should be provided\n        endomapAt :: (u -> u) -> mu -> Int -> mu\n        endomapAt f mu n = iendomap (\\ i u -> if i == n then f u else u) mu\n\n        iendomap :: (Int -> u -> u) -> mu -> mu\n\n        endounit :: Int -> u -> mu\n        endotest :: mu -> Int -> u\n\n        endoset :: mu -> Int -> u -> mu\n        endoset mu n u = endomapAt (const u) mu n\n\n        -- Probably should go somewhere else\n        endopure :: u -> mu -- Least fill with unit\n        endofill :: u -> mu -- Greatest fill with unit\n\n    -- A more or less full implementation based on `monofunctor` has been omitted\n\n\nUse is pretty much as expected, with the addition of a `@TypeApplication` to select the unit type; for example `endoset @Byte word 3 255` sets the third byte of a word to 0xFF.\n\nWith these classes, we can write `Endo` equivalents to all of our `Bits` functions. (NOTE: All of these have a presumed `@Bit` annotation a la `endomap @Bit` and so on)\n\n  * `not` = `endomap not`\n  * `and, ior, xor, nand, nor, xnor` = `endozip and, endozip ior, ...`\n  * `shift, rotate` = `endoshiftFill, endorotate`\n  * `zeroBits, oneBits` = `endofill 0, endofill 1`\n  * `bit n` = `endounit n 1`\n  * `setBit mu n` = `endoset mu n 1`\n  * `clearBit mu n` = `endoset mu n 0`\n  * `complementBit mu n` = `endomapAt (complement) mu n`\n  * `testBit mu n` = `endotest mu n`\n  * `bitSizeMaybe, bitSize` = tbd (see endocount, endocompareCount)\n  * `isSigned` = tbd\n  * `popCount` = `endofoldl (\\i u -> if u then i + 1 else i) 0`\n  * `finiteBitSize` = tbd\n  * `countLeadingZeros` = tbd\n  * `countTrailingZeros` = tbd\n\n\n\nI think this fills the gap / need for having a way to denote bit- vs byte- vs word-addressability without eg having to write a bunch of wrappers and unwrappers for accessing bits or bytes and so on. I’m still shaking things loose, but it is one of the last major pieces that I needed for replacing `ByteArray` with something like a `Bytes mu ~ Endofunctor Byte mu` based typeclass.\n\nThese classes have special meaning / relevance beyond just being somewhere in between monofunctor and functor:\n\n  * It requires `AllowAmbiguousTypes` and `TypeApplications` (ooooh spooky so startled) but has the benefit of being a functor that can choose its unit type a la `endomap @Bit complement bytes` as well as `endomap @Byte (+1) bytes`.\n  * The ability to conform to multiple element types is reminiscent of casting / coercion, _which is in the domain of / one of the identifying properties of memory_.\n  * `endomap` and `endozip` allow for _efficient_ lifting of low-level implementation of unary and binary operations respectively; they avoid going through `f (a -> b)` which isnt supported by mono- / endo- functors\n  * We could potentially use `SPECIALIZE` to implement lifting pointwise algebras for free and eg hopefully convert `endozip @Bit complement bytes` to `complement bytes` thus skipping the per-unit step and performing it in parallel (eg its faster to flip 64 bits at once than 1 bit 64 times).\n\n\n\nI’m still hacking on nomenclature, so I might use an en- prefix for endofunctors eg `enmap`, `enfold`, `enlist` and so on - or maybe an -Endo postfix eg `mapEndo`, `foldEndo`, `toListEndo`, etc - it would be good to hear some opinions on this.\n\n* * *\n\nThat is all for now! I also spent some time making class for packable Bitfields in another thread, so I probably ought to write up something about that too - next time?",
  "title": "Improving `memory` with better abstractions"
}