# Improving \`memory\` with better abstractions

**URL:** <https://discourse.haskell.org/t/improving-memory-with-better-abstractions/12350>\
**Category:** Uncategorized\
**Created:** [June 20, 2025, 10:12pm UTC](https://discourse.haskell.org/t/improving-memory-with-better-abstractions/12350 "2025-06-20T22:12:26Z")\
**Posts on this page:** 1\
**Showing post:** 29

<div class="post-metadata">

**Author:** ![ApothecaLabs](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/apothecalabs/32/3215_2.png) [@ApothecaLabs](https://discourse.haskell.org/u/ApothecaLabs)\
**Post date:** [February 21, 2026, 1:16am UTC](https://discourse.haskell.org/t/improving-memory-with-better-abstractions/12350/29 "2026-02-21T01:16:01Z")

</div>

# Two classes diverged in a codebase

Two classes diverged in a code (base),  
And sorry I could not implement both  
And be one hierarchy, long I stood  
And fiddled with laws as far as I could  
To where they forked in the undergrowth;

Then look’d the other, more often used  
And having perhaps the better claim,  
Because it was parametric content loose’d,  
Though as for that the mapping there  
Had worn them really about the same,

And both that morning equally lay  
In thunks no evaluator had trodden black.  
Oh, I kept the first for another day!  
Yet knowing how way leads on to way,  
I doubted if I should ever come back.

I shall be telling this with a sigh  
Somewhere ages and ages hence:  
Two classes diverged in a codebase, and I,  
I took neither and ran straight through the middle,  
And that has made all the difference.

* * *

This 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.

# Endofunctors

My 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`.

Enter ‘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.

I 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.

Enter `Endofunctor` ! Endo is much better characterization than polymono - it is both mathy and accurate (I hope)!

The core classes are:

```haskell
class Endofunctor u mu where
    endomap :: (u -> u) -> mu -> mu
    endozip :: (u -> u -> u) -> mu -> mu -> mu

class Endofoldable u mu where
    endofoldl :: (a -> u -> a) -> a -> mu -> a
    endofoldr :: (u -> a -> a) -> a -> mu -> a
    endofoldMap :: Monoid m => (u -> m) -> mu -> m

class (Endofunctor u mu, Endofoldable u mu) => Endotraversable u mu where
    endotraverse :: (Applicative f) => (u -> f u) -> mu -> f mu

-- Ops here are still being workshopped, I didnt mention them all for brevity
class IndexedEndofunctor u mu where

    -- A more efficient implementation for endomapAt should be provided
    endomapAt :: (u -> u) -> mu -> Int -> mu
    endomapAt f mu n = iendomap (\ i u -> if i == n then f u else u) mu

    iendomap :: (Int -> u -> u) -> mu -> mu

    endounit :: Int -> u -> mu
    endotest :: mu -> Int -> u

    endoset :: mu -> Int -> u -> mu
    endoset mu n u = endomapAt (const u) mu n

    -- Probably should go somewhere else
    endopure :: u -> mu -- Least fill with unit
    endofill :: u -> mu -- Greatest fill with unit

-- A more or less full implementation based on `monofunctor` has been omitted

```

Use 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.

With 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)

- `not` = `endomap not`
- `and, ior, xor, nand, nor, xnor` = `endozip and, endozip ior, ...`
- `shift, rotate` = `endoshiftFill, endorotate`
- `zeroBits, oneBits` = `endofill 0, endofill 1`
- `bit n` = `endounit n 1`
- `setBit mu n` = `endoset mu n 1`
- `clearBit mu n` = `endoset mu n 0`
- `complementBit mu n` = `endomapAt (complement) mu n`
- `testBit mu n` = `endotest mu n`
- `bitSizeMaybe, bitSize` = tbd (see endocount, endocompareCount)
- `isSigned` = tbd
- `popCount` = `endofoldl (\i u -> if u then i + 1 else i) 0`
- `finiteBitSize` = tbd
- `countLeadingZeros` = tbd
- `countTrailingZeros` = tbd

I 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.

These classes have special meaning / relevance beyond just being somewhere in between monofunctor and functor:

- 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`.
- 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_.
- `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
- 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).

I’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.

* * *

That is all for now! I also spent some time [making class for packable Bitfields](https://discourse.haskell.org/t/using-rgb-types-to-gain-intuition-about-type-level-programming-and-generics/13651/13) in another thread, so I probably ought to write up something about that too - next time?

---

_[View the full topic](https://discourse.haskell.org/t/improving-memory-with-better-abstractions/12350)._