Improving `memory` with better abstractions

29

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) soMonoFunctor 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:

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 in another thread, so I probably ought to write up something about that too - next time?

4 Likes